Computing Tutte Paths

DOI10.4230/LIPIcs.ICALP.2018.98zbMath1499.68288arXiv1707.05994OpenAlexW2962799941MaRDI QIDQ5002780

Jens M. Schmidt, Andreas Schmid

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1707.05994

zbMATH Keywords

Hamiltonian cycleTutte pathTutte cycle2-connected planar graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Longer cycles in essentially 4-connected planar graphs ⋮ On the Circumference of Essentially 4-connected Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some results on greedy embeddings in metric spaces
• A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs
• 3-trees with few vertices of degree 3 in circuit graphs
• A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs
• Bridges and Hamiltonian circuits in planar graphs
• 4-connected projective planar graphs are Hamiltonian
• 2-walks in circuit graphs
• Five-connected toroidal graphs are Hamiltonian
• Spanning planar subgraphs of graphs in the torus and Klein bottle
• A simple test on 2-vertex- and 2-edge-connectivity
• Longer cycles in essentially 4-connected planar graphs
• 4-connected projective-planar graphs are Hamiltonian-connected
• Hamilton paths in toroidal graphs
• 2-edge-Hamiltonian-connectedness of 4-connected plane graphs
• Computing 2-Walks in Polynomial Time
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• Disjoint paths, planarizing cycles, and spanning walks
• A Theorem on Planar Graphs
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• Hamilton cycles in plane triangulations
• On Hamilton cycles in certain planar graphs
• On longest cycles in essentially 4-connected planar graphs
• A theorem on paths in planar graphs
• A theorem on paths in planar graphs

This page was built for publication: Computing Tutte Paths