Efficient algorithms to decide tightness

Bagchi, Bhaskar, Datta, Basudeb, Burton, Benjamin A., Singh, Nitin and Spreer, Jonathan (2016). Efficient algorithms to decide tightness. In: Sandor Fekete and Anna Lubiw, 32nd International Symposium on Computational Geometry (SoCG 2016). International Symposium on Computational Geometry, Boston, MA, United States, (12:1-12:15). 14-18 June 2016. doi:10.4230/LIPIcs.SoCG.2016.12

Author Bagchi, Bhaskar
Datta, Basudeb
Burton, Benjamin A.
Singh, Nitin
Spreer, Jonathan
Title of paper Efficient algorithms to decide tightness
Conference name International Symposium on Computational Geometry
Conference location Boston, MA, United States
Conference dates 14-18 June 2016
Proceedings title 32nd International Symposium on Computational Geometry (SoCG 2016)   Check publisher's open access policy
Journal name Leibniz International Proceedings in Informatics (LIPICS)   Check publisher's open access policy
Place of Publication Wadern, Germany
Publisher Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Publication Year 2016
Sub-type Fully published paper
DOI 10.4230/LIPIcs.SoCG.2016.12
Open Access Status DOI
ISBN 9783959770095
ISSN 1868-8969
Editor Sandor Fekete
Anna Lubiw
Volume 51
Start page 12:1
End page 12:15
Total pages 15
Language eng
Abstract/Summary 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 more 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. In addition, for the more difficult problem of deciding tightness of 4-dimensional combinatorial manifolds, we describe an algorithm that is fixed parameter tractable in the treewidth of the 1-skeletons of the vertex links. Finally, we show that simpler treewidth parameters are not viable: for all non-trivial inputs, we show that the treewidths of both the 1-skeleton and the dual graph must grow too quickly for a standard treewidth-based algorithm to remain tractable.
Keyword Discrete geometry and topology
Polynomial time algorithms
Fixed parameter tractability
Tight triangulations
Simplicial complexes
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Conference Paper
Sub-type: Fully published paper
Collections: School of Mathematics and Physics
HERDC Pre-Audit
Version Filter Type
Citation counts: Scopus Citation Count Cited 2 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 15 Jun 2016, 15:40:02 EST by Dr Benjamin Burton on behalf of Mathematics