2026-08-11T17:50:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5904 2024-03-06T10:37:15Z ddc:004 open_access

Efficient Algorithms to Decide Tightness Bagchi, Bhaskar Datta, Basudeb Burton, Benjamin A. Singh, Nitin Spreer, Jonathan discrete geometry and topology polynomial time algorithms fixed parameter tractability tight triangulations simplicial complexes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bhaskar Bagchi and Basudeb Datta and Benjamin A. Burton and Nitin Singh and Jonathan Spreer 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.12 urn:nbn:de:0030-drops-59040 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.12 eng https://creativecommons.org/licenses/by/3.0/legalcode