Options
Computing tutte paths
Publikationstyp
Conference Paper
Date Issued
2018-07
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
107
Article Number
98
Citation
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 107: 98 (2018)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
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 [5] 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 [24]. 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 e cient algorithm that computes a Tutte path (in this unrestricted setting). One of the strongest existence results about such Tutte paths is due to Sanders [23], 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 e ciently. Our method refines both, the existence results of Thomassen [29] and Sanders [23], 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(n2).
Subjects
2-connected planar graph
Hamiltonian cycle
Tutte cycle
Tutte path