Volume 20, issue 2 (2016)

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

Volume 28, 1 issue

Volume 27, 9 issues

Volume 26, 8 issues

Volume 25, 7 issues

Volume 24, 7 issues

Volume 23, 7 issues

Volume 22, 7 issues

Volume 21, 6 issues

Volume 20, 6 issues

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
Policies for Authors
Ethics Statement
ISSN (electronic): 1364-0380
ISSN (print): 1465-3060
Author Index
To Appear
Other MSP Journals
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

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.

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
Received: 16 October 2014
Accepted: 28 June 2015
Published: 28 April 2016
Proposed: Cameron Gordon
Seconded: Dmitri Burago, Bruce Kleiner
Benjamin A Burton
School of Mathematics and Physics
The University of Queensland
Brisbane QLD 4072
Éric Colin de Verdière
Département d’informatique
École normale supérieure, CNRS
45 rue d’Ulm
75005 Paris
Arnaud de Mesmay
11 rue des Mathématiques
Grenoble Campus BP46
F-38402 Saint Martin-d’Hères