A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

DOI10.7155/JGAA.00445MaRDI QIDQ5367029zbMATH OpenOpenAlexFDO

Authors Éric Colin de Verdière, Vojtěch Kaluža, Pavel Paták, Zuzana Safernova, Martin Tancer

Publication date 12 October 2017

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani-Tutte drawing on the projective plane into an embedding.

Recommendations

• A direct proof of the strong Hanani-Tutte theorem on the projective plane
• Strong Hanani–Tutte on the Projective Plane
• On the strong Hanani-Tutte theorem
• A combinatorial proof of a stronger dense Hindman theorem
• scientific article; zbMATH DE number 493018
• Proof of a conjecture on the strong chromatic index of Halin graphs
• Hajós' conjecture and projective graphs
• A purely combinatorial proof of the Hadwiger Debrunner \((p,q)\) conjecture
• A shorter proof of Thomassen's theorem on Tutte paths in plane graphs
• A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem

Cited in

(7)

• Level-planarity: transitivity vs. even crossings
• The \(\mathbb{Z}_2\)-genus of Kuratowski minors
• A direct proof of the strong Hanani-Tutte theorem on the projective plane
• Strong Hanani–Tutte on the Projective Plane
• scientific article; zbMATH DE number 7559239 (Why is no real title available?)
• The $\mathbb{Z}_2$-genus of Kuratowski minors
• Strong Hanani-Tutte for the torus

This page was built for publication: A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5367029)