The complexity of detecting taut angle structures on triangulations

Burton, Benjamin and Spreer, Jonathan (2013). The complexity of detecting taut angle structures on triangulations. In: Sanjeev Khanna, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, United States, (168-183). 6-9 January 2013.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
Author Burton, Benjamin
Spreer, Jonathan
Title of paper The complexity of detecting taut angle structures on triangulations
Conference name 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
Conference location New Orleans, United States
Conference dates 6-9 January 2013
Proceedings title Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
Journal name Proceedings of the Annual ACM - SIAM Symposium on Discrete Algorithms
Place of Publication Philadelphia, United States
Publisher Society for Industrial and Applied Mathematics
Publication Year 2013
Sub-type Fully published paper
Open Access Status
ISBN 9781611972511
9781611972528
ISSN 1071-9040
2160-1445
1557-9468
Editor Sanjeev Khanna
Volume 143
Start page 168
End page 183
Total pages 16
Collection year 2014
Language eng
Abstract/Summary The are many fundatmental algorithmic problems on triangulated 3-manifolds whose complexties are unknown. Here we study the problem of finding a taut angle structure on a 3-manifold triangulation, whose existence has implications for both the geometry and combinatories of the triangulation. We prove that detecting taut angle structures is NP-complete, but also fixed-parameter tractalbe in the treewidth of the face pairing graph of the traiangulation. These results have deeper implications: the core techniques can serve as a launching point for approaching key decision problems suck as unknot recognition and prime decomposition of 3-manifolds.
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2014 Collection
 
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Google Scholar Search Google Scholar
Created: Thu, 02 May 2013, 14:32:59 EST by Jonathan Spreer on behalf of Mathematics