Volume 20, issue 2 (2016)

Download this article
Download this article For screen
For printing
Recent Issues

Volume 20
Issue 4, 1807–2438
Issue 3, 1257–1806
Issue 2, 629–1255
Issue 1, 1–627

Volume 19, 6 issues

Volume 18, 5 issues

Volume 17, 5 issues

Volume 16, 4 issues

Volume 15, 4 issues

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 5 issues

Volume 11, 4 issues

Volume 10, 4 issues

Volume 9, 4 issues

Volume 8, 3 issues

Volume 7, 2 issues

Volume 6, 2 issues

Volume 5, 2 issues

Volume 4, 1 issue

Volume 3, 1 issue

Volume 2, 1 issue

Volume 1, 1 issue

The Journal
About the Journal
Editorial Board
Editorial Interests
Editorial Procedure
Submission Guidelines
Submission Page
Subscriptions
Author Index
To Appear
Contacts
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
On the complexity of immersed normal surfaces

Benjamin A Burton, Éric Colin de Verdière and Arnaud de Mesmay

Geometry & Topology 20 (2016) 1061–1083
Abstract

Normal surface theory, a tool to represent surfaces in a triangulated 3–manifold combinatorially, is ubiquitous in computational 3–manifold theory. In this paper, we investigate a relaxed notion of normal surfaces where we remove the quadrilateral conditions. This yields normal surfaces that are no longer embedded. We prove that it is NP-hard to decide whether such a surface is immersed. Our proof uses a reduction from Boolean constraint satisfaction problems where every variable appears in at most two clauses, using a classification theorem of Feder. We also investigate variants, and provide a polynomial-time algorithm to test for a local version of this problem.

Keywords
low-dimensional topology, normal surface, immersed normal surface, constraint satisfaction problem, three-manifold, computational complexity
Mathematical Subject Classification 2010
Primary: 57N10, 68Q17
Secondary: 57Q35, 68U05
References
Publication
Received: 16 October 2014
Accepted: 28 June 2015
Published: 28 April 2016
Proposed: Cameron Gordon
Seconded: Dmitri Burago, Bruce Kleiner
Authors
Benjamin A Burton
School of Mathematics and Physics
The University of Queensland
Brisbane QLD 4072
Australia
http://www.maths.uq.edu.au/~bab/
Éric Colin de Verdière
Département d’informatique
École normale supérieure, CNRS
45 rue d’Ulm
75005 Paris
France
http://www.di.ens.fr/~colin/
Arnaud de Mesmay
CNRS
GIPSA-lab
11 rue des Mathématiques
Grenoble Campus BP46
F-38402 Saint Martin-d’Hères
France
http://www.gipsa-lab.fr/~arnaud.demesmay