Geometry & Topology Volume 20, issue 2 (2016)

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1364-0380 (online)

ISSN 1465-3060 (print)

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

DOI: 10.2140/gt.2016.20.1061

Bibliography

1	I Agol, J Hass, W Thurston, The computational complexity of knot genus and spanning area, Trans. Amer. Math. Soc. 358 (2006) 3821 MR2219001
2	I R Aitchison, S Matsumoto, J H Rubinstein, Surfaces in the figure-8 knot complement, J. Knot Theory Ramifications 7 (1998) 1005 MR1671559
3	S Arora, B Barak, Computational complexity: a modern approach, Cambridge Univ. Press (2009) MR2500087
4	B A Burton, T Lewiner, J Paixão, J Spreer, Parameterized complexity of discrete Morse theory, from: "Computational geometry", Association for Computing Machinery (2013) 127 MR3208204
5	B A Burton, J Spreer, The complexity of detecting taut angle structures on triangulations, from: "Proceedings of the 24th Annual ACM–SIAM Symposium on Discrete Algorithms", Society for Industrial and Applied Mathematics (2012) 168 MR3185388
6	É Colin de Verdière, Topological algorithms for graphs on surfaces, Habilitation thesis, École normale supérieure (2012)
7	N Creignou, S Khanna, M Sudan, Complexity classifications of Boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics (2001) MR1827376
8	V Dalmau, D K Ford, Generalized satisfiability with limited occurrences per variable: a study through delta-matroid parity, from: "Mathematical foundations of computer science" (editors B Rovan, P Vojtáš), Lecture Notes in Comput. Sci. 2747, Springer (2003) 358 MR2081586
9	T Feder, Fanout limitations on constraint systems, Theoret. Comput. Sci. 255 (2001) 281 MR1819077
10	M R Fellows, Parameterized complexity: new developments and research frontiers, from: "Aspects of complexity" (editors R Downey, D Hirschfeldt), de Gruyter Ser. Log. Appl. 4, de Gruyter (2001) 51 MR1884261
11	C Gordon, The theory of normal surfaces, lecture notes (2001)
12	W Haken, Theorie der Normalflächen, Acta Math. 105 (1961) 245 MR0141106
13	J Hass, J C Lagarias, N Pippenger, The computational complexity of knot and link problems, J. ACM 46 (1999) 185 MR1693203
14	A Hatcher, Notes on basic 3–manifold topology, (2007)
15	G Kuperberg, Knottedness is in NP, modulo GRH, Adv. Math. 256 (2014) 493 MR3177300
16	D M Letscher, Immersed normal surfaces and decision problems for 3–manifolds, PhD thesis, University of Michigan (1997)
17	J Matoušek, B Gärtner, Understanding and using linear programming, Springer (2007)
18	S Matsumoto, R Rannard, The regular projective solution space of the figure-eight knot complement, Experiment. Math. 9 (2000) 221 MR1780207
19	E E Moise, Affine structures in 3–manifolds, V : The triangulation theorem and Hauptvermutung, Ann. of Math. 56 (1952) 96 MR0048805
20	R Rannard, Computing immersed normal surfaces in the figure-eight knot complement, Experiment. Math. 8 (1999) 73 MR1685039
21	T J Schaefer, The complexity of satisfiability problems, from: "Tenth Annual ACM Symposium on Theory of Computing", ACM (1978) 216 MR521057
22	A Schrijver, Combinatorial optimization : polyhedra and efficiency, Volume A, 24, Springer (2003) MR1956924
23	J Stillwell, Classical topology and combinatorial group theory, 72, Springer (1993) MR1211642