Computing Tutte Paths

Authors Andreas Schmid, Jens M. Schmidt



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.98.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Schmid
  • Max Planck Institute for Informatics, Saarbrücken, Germany
Jens M. Schmidt
  • Technische Universität Ilmenau, Ilmenau, Germany

Cite AsGet BibTex

Andreas Schmid and Jens M. Schmidt. Computing Tutte Paths. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.98

Abstract

Tutte paths are one of the most successful tools for attacking problems on long cycles in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps prevent any attempt to bound the running time by a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki [N. Chiba and T. Nishizeki, 1989] showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a significantly more complicated structure, and it has only recently been shown that they can be computed in polynomial time [A. Schmid and J. M. Schmidt, 2015]. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. In this unrestricted setting, no computational results for Tutte paths are known. We give the first efficient algorithm that computes a Tutte path (in this unrestricted setting). One of the strongest existence results about such Tutte paths is due to Sanders [D. P. Sanders, 1997], which allows one to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute such a special Tutte path efficiently. Our method refines both, the existence results of Thomassen [C. Thomassen, 1983] and Sanders [D. P. Sanders, 1997], and avoids that the subgraphs arising in the inductive proof intersect in more than one edge by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in time O(n^2).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Tutte Path
  • Tutte Cycle
  • 2-Connected Planar Graph
  • Hamiltonian Cycle

Metrics

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

References

  1. T. Asano, S. Kikuchi, and N. Saito. A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs. Discrete Applied Mathematics, 7(1):1-15, 1984. Google Scholar
  2. G. Brinkmann and C. T. Zamfirescu. A Strengthening of a Theorem of Tutte on Hamiltonicity of Polyhedra. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1606.01693.
  3. R. Brunet, M. N. Ellingham, Z. C. Gao, A. Metzlar, and R. B. Richter. Spanning planar subgraphs of graphs in the torus and Klein bottle. Journal of Combinatorial Theory, Series B, 65(1):7-22, 1995. URL: http://dx.doi.org/10.1006/jctb.1995.1041.
  4. N. Chiba and T. Nishizeki. A theorem on paths in planar graphs. Journal of Graph Theory, 10(4):449-450, 1986. Google Scholar
  5. N. Chiba and T. Nishizeki. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs. Journal of Algorithms, 10(2):187-211, 1989. Google Scholar
  6. R. Diestel. Graph Theory. Springer, fourth edition, 2010. Google Scholar
  7. I. Fabrici, J. Harant, and S. Jendrol. On longest cycles in essentially 4-connected planar graphs. Discussiones Mathematicae Graph Theory, 36:565-575, 2016. Google Scholar
  8. I. Fabrici, J. Harant, S. Mohr, and J. M. Schmidt. Longer cycles in essentially 4-connected planar graphs. Discussiones Mathematicae Graph Theory, to appear. Google Scholar
  9. Z. Gao and R. B. Richter. 2-Walks in circuit graphs. Journal of Combinatorial Theory, Series B, 62(2):259-267, 1994. Google Scholar
  10. Z. Gao, R. B. Richter, and X. Yu. 2-Walks in 3-connected planar graphs. Australasian Journal of Combinatorics, 11:117-122, 1995. Google Scholar
  11. Z. Gao, R. B. Richter, and X. Yu. Erratum to: 2-Walks in 3-connected planar graphs. Australasian Journal of Combinatorics, 36:315-316, 2006. Google Scholar
  12. D. Gouyou-Beauchamps. The Hamiltonian circuit problem is polynomial for 4-connected planar graphs. SIAM Journal on Computing, 11(3):529-539, 1982. Google Scholar
  13. J. Harant and S. Senitsch. A generalization of Tutte’s theorem on Hamiltonian cycles in planar graphs. Discrete Mathematics, 309(15):4949-4951, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.04.038.
  14. F. Harary and G. Prins. The block-cutpoint-tree of a graph. Publ. Math. Debrecen, 13:103-107, 1966. Google Scholar
  15. B. Jackson and N. C. Wormald. k-Walks of graphs. Australasian Journal of Combinatorics, 2:135-146, 1990. Google Scholar
  16. B. Jackson and X. Yu. Hamilton cycles in plane triangulations. Journal of Graph Theory, 41(2):138-150, 2002. Google Scholar
  17. K. Kawarabayashi and K. Ozeki. 4-connected projective-planar graphs are Hamiltonian-connected. Journal of Combinatorial Theory, Series B, 112:36-69, 2015. Google Scholar
  18. Tom Leighton and Ankur Moitra. Some results on greedy embeddings in metric spaces. Discrete & Computational Geometry, 44(3):686-705, Oct 2010. URL: http://dx.doi.org/10.1007/s00454-009-9227-6.
  19. A. Nakamoto, Y. Oda, and K. Ota. 3-trees with few vertices of degree 3 in circuit graphs. Discrete Mathematics, 309(4):666-672, 2009. URL: http://dx.doi.org/10.1016/j.disc.2008.01.002.
  20. K. Ozeki. A shorter proof of Thomassen’s theorem on Tutte paths in plane graphs. SUT Journal of Mathematics, 50:417-425, 2014. URL: http://comb.math.keio.ac.jp/ozeki.
  21. K. Ozeki and P. Vrána. 2-edge-Hamiltonian-connectedness of 4-connected plane graphs. European Journal of Combinatorics, 35:432-448, 2014. URL: http://dx.doi.org/10.1016/j.ejc.2013.06.033.
  22. D. P. Sanders. On Hamilton cycles in certain planar graphs. Journal of Graph Theory, 21(1):43-50, 1996. Google Scholar
  23. D. P. Sanders. On paths in planar graphs. Journal of Graph Theory, 24(4):341-345, 1997. URL: http://dx.doi.org/10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O.
  24. A. Schmid and J. M. Schmidt. Computing 2-walks in polynomial time. In Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 676-688, 2015. Google Scholar
  25. J. M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Information Processing Letters, 113(7):241-244, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.01.016.
  26. R. Thomas and X. Yu. 4-connected projective-planar graphs are Hamiltonian. Journal of Combinatorial Theory, Series B, 62(1):114-132, 1994. Google Scholar
  27. R. Thomas and X. Yu. Five-connected toroidal graphs are Hamiltonian. Journal of Combinatorial Theory, Series B, 69(1):79-96, 1997. Google Scholar
  28. R. Thomas, X. Yu, and W. Zang. Hamilton paths in toroidal graphs. Journal of Combinatorial Theory, Series B, 94(2):214-236, 2005. Google Scholar
  29. C. Thomassen. A theorem on paths in planar graphs. Journal of Graph Theory, 7(2):169-176, 1983. Google Scholar
  30. W. T. Tutte. A theorem on planar graphs. Transactions of the American Mathematical Society, 82:99-116, 1956. Google Scholar
  31. W. T. Tutte. Bridges and Hamiltonian circuits in planar graphs. Aequationes Mathematicae, 15(1):1-33, 1977. Google Scholar
  32. H. Whitney. A theorem on graphs. Annals of Mathematics, 32(2):378-390, 1931. Google Scholar
  33. X. Yu. Disjoint paths, planarizing cycles, and spanning walks. Transactions of the American Mathematical Society, 349(4):1333-1358, 1997. 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