Document Open Access Logo

Finding Tutte Paths in Linear Time

Authors Therese Biedl , Philipp Kindermann

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.23.pdf
  • Filesize: 0.87 MB
  • 14 pages

Document Identifiers

Author Details

Therese Biedl
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Philipp Kindermann
  • Lehrstuhl für Informatik I, Universität Würzburg, Germany

Funding

  • Biedl, Therese: Supported by NSERC.

Cite As Get BibTex

Therese Biedl and Philipp Kindermann. Finding Tutte Paths in Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.23

Abstract

It is well-known that every planar graph has a Tutte path, i.e., a path P such that any component of G-P has at most three attachment points on P. However, it was only recently shown that such Tutte paths can be found in polynomial time. In this paper, we give a new proof that 3-connected planar graphs have Tutte paths, which leads to a linear-time algorithm to find Tutte paths. Furthermore, our Tutte path has special properties: it visits all exterior vertices, all components of G-P have exactly three attachment points, and we can assign distinct representatives to them that are interior vertices. Finally, our running time bound is slightly stronger; we can bound it in terms of the degrees of the faces that are incident to P. This allows us to find some applications of Tutte paths (such as binary spanning trees and 2-walks) in linear time as well.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • planar graph
  • Tutte path
  • Hamiltonian path
  • 2-walk
  • linear time

Metrics

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

Related Versions

References

  1. Takao Asano, Shunji Kikuchi, and Nobuji Saito. A Linear Algorithm for Finding Hamiltonian Cycles in 4-Connected Maximal Planar Graphs. Discrete Applied Mathematics, 7:1-15, 1985. URL: http://dx.doi.org/10.1016/0166-218X(84)90109-4.
  2. David W. Barnette. Trees in Polyhedral Graphs. Canadian Journal of Mathematics, 18:731-736, 1966. URL: http://dx.doi.org/10.4153/CJM-1966-073-4.
  3. Therese Biedl. Trees and Co-trees with Bounded Degrees in Planar 3-Connected Graphs. In R. Ravi and Inge Li Gørtz, editors, Scandinavian Symposium and Workshops on Algorithms Theory (SWAT'14), volume 8503 of Lecture Notes in Computer Science, pages 62-73. Springer-Verlag, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08404-6_6.
  4. Therese Biedl and Martin Derka. 1-String B₂-VPG-Representations of Planar Graphs. Journal on Computational Geometry, 7(2):191-215, 2016. URL: http://dx.doi.org/10.20382/jocg.v7i2a8.
  5. Therese Biedl and Philipp Kindermann. Finding Tutte Paths in Linear Time. Arxiv report, abs/1812.04543, 2018. URL: http://arxiv.org/abs/1812.04543.
  6. Giuseppe Di Battista and Roberto Tamassia. Incremental Planarity Testing. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS'89), pages 436-441. IEEE Computer Society, 1989. URL: http://dx.doi.org/10.1109/SFCS.1989.63515.
  7. Reinhard Diestel. Graph Theory, 5th Edition, volume 173 of Graduate Texts in Mathematics. Springer, 2016. URL: http://diestel-graph-theory.com/.
  8. Zhicheng Gao and R. Bruce Richter. 2-Walks in Circuit Graphs. Journal of Combinatorial Theory, Series B, 62(2):259-267, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1068.
  9. Carsten Gutwenger and Petra Mutzel. A Linear Time Implementation of SPQR-Trees. In Joe Marks, editor, Proceedings of the 8th International Symposium on Graph Drawing (GD'00), volume 1984 of Lecture Notes in Computer Science, pages 77-90. Springer, 2000. URL: http://dx.doi.org/10.1007/3-540-44541-2_8.
  10. John E. Hopcroft and Robert E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135-158, 1973. URL: http://dx.doi.org/10.1137/0202012.
  11. Ken-ichi Kawarabayashi and Kenta Ozeki. 4-Connected Projective-Planar Graphs Are Hamiltonian-Connected. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pages 378-395. Society for Industrial and Applied Mathematics, 2013. URL: http://dx.doi.org/10.1016/j.jctb.2012.11.004.
  12. Daniel 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.
  13. Andreas Schmid and Jens M. Schmidt. Computing 2-Walks in Polynomial Time. In Ernst W. Mayr and Nicolas Ollinger, editors, Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS'15), volume 30 of LIPIcs, pages 676-688. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.676.
  14. Andreas Schmid and Jens M. Schmidt. Computing 2-Walks in Polynomial Time. ACM Transactions on Algorithms, 14(2):22:1-22:18, 2018. URL: http://dx.doi.org/10.1145/3183368.
  15. Andreas Schmid and Jens M. Schmidt. Computing Tutte Paths. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, Proceedings of the 45th International Colloquium on Algorithms, Languages and Programming (ICALP'18), volume 107 of LIPIcs, pages 98:1-98:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.98.
  16. Willy-Bernhard Strothmann. Bounded-Degree Spanning Trees. Ph.d. thesis, Universität Paderborn, Heinz Nixdorf Institut, Theoretische Informatik, Paderborn, 1997. ISBN 3-931466-34-5. URL: https://www.hni.uni-paderborn.de/pub/468.
  17. Robin Thomas and Xingxing Yu. 4-Connected Projective-Planar Graphs Are Hamiltonian. Journal of Combinatorial Theory, Series B, 62:114-132, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1058.
  18. Carsten Thomassen. A Theorem on Paths in Planar Graphs. Journal of Graph Theory, 7(2):169-176, 1983. URL: http://dx.doi.org/10.1002/jgt.3190070205.
  19. William T. Tutte. Bridges and Hamiltonian Circuits in Planar Graphs. Aequationes Mathematicae, 15(1):1-33, 1977. URL: http://dx.doi.org/10.1007/BF01837870.
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