Computing 2-Walks in Polynomial Time

Authors Andreas Schmid, Jens M. Schmidt



PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.676.pdf
  • Filesize: 1.27 MB
  • 13 pages

Document Identifiers

Author Details

Andreas Schmid
Jens M. Schmidt

Cite AsGet BibTex

Andreas Schmid and Jens M. Schmidt. Computing 2-Walks in Polynomial Time. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 676-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.STACS.2015.676

Abstract

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.
Keywords
  • algorithms and data structures
  • 2-walks
  • 3-connected planar graphs
  • Tutte paths
  • 3-trees

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. D. Barnette. Trees in polyhedral graphs. Canadian Journal of Mathematics, 18:731-736, 1966. Google Scholar
  3. T. Biedl. Trees and co-trees with bounded degrees in planar 3-connected graphs. In 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'14), pages 62-73, 2014. Google Scholar
  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. Z. Gao and R. B. Richter. 2-Walks in circuit graphs. Journal of Combinatorial Theory, Series B, 62(2):259-267, 1994. Google Scholar
  8. 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
  9. 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
  10. M. R. Garey, D. S. Johnson, and R. E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput., 5(4):704-714, 1976. Google Scholar
  11. 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
  12. F. Harary and G. Prins. The block-cutpoint-tree of a graph. Publ. Math. Debrecen, 13:103-107, 1966. Google Scholar
  13. B. Jackson and N. C. Wormald. k-Walks of graphs. Australasian Journal of Combinatorics, 2:135-146, 1990. Google Scholar
  14. W.-B. Strothmann. Bounded degree spanning trees. PhD thesis, FB Mathematik/Informatik und Heinz Nixdorf Institut, Universität-Gesamthochschule Paderborn, 1997. Google Scholar
  15. C. Thomassen. A theorem on paths in planar graphs. Journal of Graph Theory, 7(2):169-176, 1983. Google Scholar
  16. W. T. Tutte. A theorem on planar graphs. Transactions of the American Mathematical Society, 82:99-116, 1956. Google Scholar
  17. H. Whitney. A theorem on graphs. Annals of Mathematics, 32(2):378-390, 1931. Google Scholar
  18. H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34(1):339-362, 1932. 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