Name
Abstract | ||
|---|---|---|
Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of $3$-manifolds -- a problem which previously was thought to be hard. Furthermore, we describe an algorithm to decide general tightness in the case of $4$-dimensional combinatorial manifolds which is fixed parameter tractable in the treewidth of the $1$-skeletons of their vertex links, and we present an algorithm to decide $\mathbb{F}_2$-tightness for weak pseudomanifolds $M$ of arbitrary but fixed dimension which is fixed parameter tractable in the treewidth of the dual graph of $M$. |
Year | Venue | Field |
|---|---|---|
2014 | Symposium on Computational Geometry | Discrete mathematics,Combinatorics,Convexity,Vertex (geometry),Computer science,Algorithm,Regular polygon,Dual graph,Simplicial complex,Treewidth,Time complexity,Manifold |
DocType | Volume | Citations |
Journal | abs/1412.1547 | 3 |
PageRank | References | Authors |
0.51 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bhaskar Bagchi | 1 | 3 | 0.51 |
| Benjamin A. Burton | 2 | 172 | 25.57 |
| Basudeb Datta | 3 | 64 | 13.91 |
| Nitin Singh | 4 | 10 | 1.85 |
| Jonathan Spreer | 5 | 3 | 0.51 |