Volume 20, issue 2 (2016)

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

Volume 21
Issue 6, 3191–3810
Issue 5, 2557–3190
Issue 4, 1931–2555
Issue 3, 1285–1930
Issue 2, 647–1283
Issue 1, 1–645

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
Subscriptions
Editorial Board
Editorial Interests
Editorial Procedure
Submission Guidelines
Submission Page
Author Index
To Appear
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