On the strong Hanani-Tutte theorem

DOI10.37236/8903MaRDI QIDQ2656896zbMATH OpenOpenAlexFDO

Authors Hooman R. Dehkordi, Graham Farr

Publication date 17 March 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/8903

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

non-separatingplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83)

Review text

A non-separating drawing of a graph is a drawing of the graph that does not contain any separating cycles. A non-separating planar graph is a graph that has a non-separating planar drawing. If every two vertex-disjoint edges in \(D\) cross an even number of times, or if there is a chordless decomposing cycle that decomposes \(D\) into two evenly decomposable drawings, then a drawing \(D\) is evenly decomposable. In this paper, the authors prove that if \(D\) is a non-separating drawing of a graph \(G\) such that any two vertex-disjoint edges in \(D\) cross each other an even number of times, then \(G\) is a non-separating planar graph. Then they use the result to prove a stronger version of the Hanani-Tutte theorem. It is that if \(D\) is an evenly decomposable drawing of a graph \(G\) on the plane, then \(G\) is planar and there is a planar drawing \(D^\prime\) of \(G\) such that any decomposing chordless cycle \(C\) in \(S\) separates vertices \(u\) and \(v\) in \(D^\prime\) if and only if \(C\) separates \(u\) and \(v\) in \(D\).

Recommendations

• Unified Hanani-Tutte theorem
• Strong Hanani–Tutte on the Projective Plane
• scientific article; zbMATH DE number 5763167
• Removing even crossings
• Towards the Hanani-Tutte theorem for clustered graphs

Cites work

• Bounds for generalized thrackles
• Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4
• scientific article; zbMATH DE number 2107976 (Why is no real title available?)
• Invariants of Graphs in Three-Space
• Non-separating planar graphs
• On the optimality of the Arf invariant formula for graph polynomials
• Removing even crossings on surfaces
• Strong Hanani–Tutte on the Projective Plane
• Toward a theory of crossing numbers
• Unified Hanani-Tutte theorem

Cited in

(8)

• Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4
• Unified Hanani-Tutte theorem
• Towards the Hanani-Tutte theorem for clustered graphs
• A direct proof of the strong Hanani-Tutte theorem on the projective plane
• Removing Even Crossings on Surfaces
• Strong Hanani–Tutte on the Projective Plane
• Hanani-Tutte and related results
• A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane

This page was built for publication: On the strong Hanani-Tutte theorem

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