Document Open Access Logo

Finding Non-Orientable Surfaces in 3-Manifolds

Authors Benjamin A. Burton, Arnaud de Mesmay, Uli Wagner

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.24.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Benjamin A. Burton
Arnaud de Mesmay
Uli Wagner

Cite As Get BibTex

Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. Finding Non-Orientable Surfaces in 3-Manifolds. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.24

Abstract

We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds.

We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.

Subject Classification

Keywords
  • 3-manifold
  • low-dimensional topology
  • embedding
  • non-orientability
  • normal surfaces

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ian Agol, Joel Hass, and William Thurston. The computational complexity of knot genus and spanning area. Transactions of the American Mathematical Society, 358:3821-3850, 2006. Google Scholar
  2. Glen E. Bredon and John W. Wood. Non-orientable surfaces in orientable 3-manifolds. Invent. Math., 7:83-110, 1969. Google Scholar
  3. Benjamin A. Burton. A new approach to crushing 3-manifold triangulations. Discrete &Computational Geometry, 52(1):116-139, 2014. Google Scholar
  4. Benjamin A. Burton, Arnaud de Mesmay, and Uli Wagner. Finding non-orientable surfaces in 3-manifolds. arXiv:1602.07907, 2016. Google Scholar
  5. Benjamin A. Burton and Melih Ozlen. Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Softw., 39(1):4:1-4:18, November 2012. Google Scholar
  6. Werner End. Non-orientable surfaces in 3-manifolds. Archiv der Mathematik, 59(2):173-185, 1992. Google Scholar
  7. Wolfgang Haken. Theorie der Normalflachen, ein Isotopiekriterium für den Kreisnoten. Acta Mathematica, 105:245-375, 1961. Google Scholar
  8. Joel Hass. What is an almost normal surface. arXiv:1208.0568v1, 2012. Google Scholar
  9. Joel Hass and Greg Kuperberg. New results on the complexity of recognizing the 3-sphere. In Oberwolfach Reports, volume 9, pages 1425-1426, 2012. Google Scholar
  10. Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger. The computational complexity of knot and link problems. Journal of the ACM, 46(2):185-211, 1999. Google Scholar
  11. Allen Hatcher. Algebraic topology. Cambridge University Press, 2002. Available at URL: http://www.math.cornell.edu/~hatcher/.
  12. Allen Hatcher. Notes on basic 3-manifold topology. Notes available on the author’s webpage, 2007. Google Scholar
  13. John Hempel. 3-manifolds. AMS Chelsea Publishing, Providence, RI, 2004. Reprint of the 1976 original. Google Scholar
  14. Miwa Iwakura and Chuichiro Hayashi. Non-orientable fundamental surfaces in lens spaces. Topology and its Applications, 156(10):1753-1766, 2009. Google Scholar
  15. William Jaco and Ulrich Oertel. An algorithm to decide if a 3-manifold is a Haken manifold. Topology, 23(2):195-209, 1984. Google Scholar
  16. William Jaco and J. Hyam Rubinstein. 0-efficient triangulations of 3-manifolds. Journal of Differential Geometry, 65:61-168, 2003. Google Scholar
  17. William H Jaco and Peter B Shalen. Seifert fibered spaces in 3-manifolds, volume 220. American Mathematical Society, 1979. Google Scholar
  18. K Johannson. Homotopy equivalence of 3-manifolds with boundary. Lecture Notes in Math, 761, 1979. Google Scholar
  19. Paik Kee Kim. Some 3-manifolds which admit Klein bottles. Transactions of the American Mathematical Society, 244:299-312, 1978. Google Scholar
  20. Hellmuth Kneser. Geschlossene Flächen in dreidimensionalen Mannigfaltigkeiten. Jahresbericht Math. Verein., 28:248-260, 1929. Google Scholar
  21. Greg Kuperberg. Knottedness is in NP, modulo GRH. Advances in Mathematics, 256:493-506, 2014. Google Scholar
  22. Greg Kuperberg. Algorithmic homeomorphism of 3-manifolds as a corollary of geometrization. arXiv:1508.06720, 2015. Google Scholar
  23. Adam Levine, Daniel Ruberman, and Sašo Strle. Nonorientable surfaces in homology cobordisms. Geometry &Topology, 19(1):439-494, 2015. Google Scholar
  24. Tao Li. Heegaard surfaces and measured laminations, I: the Waldhausen conjecture. Inventiones mathematicae, 167(1):135-177, 2007. Google Scholar
  25. Tao Li. An algorithm to determine the Heegaard genus of a 3-manifold. Geometry &Topology, 15(2):1029-1106, 2011. Google Scholar
  26. Jiří Matousšek, Martin Tancer, and Uli Wagner. Hardness of embedding simplicial complexes in R^d. Journal of the European Mathematical Society, 13(2):259-295, 2011. Google Scholar
  27. Jiří Matoušek, Eric Sedgwick, Martin Tancer, and Uli Wagner. Embeddability in the 3-sphere is decidable. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry, SOCG'14, pages 78:78-78:84, New York, NY, USA, 2014. ACM. Google Scholar
  28. Sergei V. Matveev. Algorithmic topology and classification of 3-manifolds, volume 9 of Algorithms and Computation in Mathematics. Springer-Verlag, 2003. Google Scholar
  29. Edwin E. Moise. Affine structures in 3-manifolds. V. The triangulation theorem and Hauptvermutung. Ann. of Math. (2), 56:96-114, 1952. Google Scholar
  30. Richard Rannard. Incompressible surfaces in Seifert fibered spaces. Topology and its Applications, 72(1):19-30, 1996. Google Scholar
  31. Joachim Hyam Rubinstein. On 3-manifolds that have finite fundamental group and contain Klein bottles. Transactions of the American Mathematical Society, 251:129-137, 1979. Google Scholar
  32. Joachim Hyam Rubinstein. Nonorientable surfaces in some non-Haken 3-manifolds. Transactions of the American Mathematical Society, 270(2):503-524, 1982. Google Scholar
  33. Joachim Hyam Rubinstein. An algorithm to recognize the 3-sphere. In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994), pages 601-611, Basel, 1995. Birkhäuser. Google Scholar
  34. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  35. Saul Schleimer. Sphere recognition lies in NP. In Michael Usher, editor, Low-dimensional and Symplectic Topology, volume 82, pages 183-214. American Mathematical Society, 2011. Google Scholar
  36. A. B. Skopenkov. Embedding and knotting of manifolds in euclidean spaces. In Nicholas Young and Yemon Choi, editors, Surveys in Contemporary Mathematics, pages 248-342. Cambridge University Press, 2007. Cambridge Books Online. Google Scholar
  37. A.B. Skopenkov. A generalization of Neuwirth’s theorem on thickening 2-dimensional polyhedra. Mathematical Notes, 58(5):1244-1247, 1995. Google Scholar
  38. Carsten Thomassen. The graph genus problem is NP-complete. Journal of Algorithms, 10(4):568-576, 1989. Google Scholar
  39. Abigail Thompson. Thin position and the recognition problem for S³. Mathematical Research Letters, 1:613-630, 1994. Google Scholar
  40. Uli Wagner. Minors in random and expanding hypergraphs. In Proceedings of the Twenty-Seventh Annual Sympoisum on Computational Geometry, pages 351-360, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact