A graph is planar if it has a drawing in which no two edges cross. The Hanani-Tutte Theorem states that a graph is planar if it has a drawing $D$ such that any two edges in $D$ cross an even number of times. A graph $G$ is a non-separating planar graph if it has a drawing $D$ such that (1) edges do not cross in $D$, and (2) for any cycle $C$ and any two vertices $u$ and $v$ that are not in $C$, $u$ and $v$ are on the same side of $C$ in $D$. Non-separating planar graphs are closed under taking minors and hence have a finite forbidden minor characterisation. In this paper, we prove a Hanani-Tutte type theorem for non-separating planar graphs. We use this theorem to prove a stronger version of the strong Hanani-Tutte Theorem for planar graphs, namely that a graph is planar if it has a drawing in which any two disjoint edges cross an even number of times or it has a chordless cycle that enables a suitable decomposition of the graph.
@article{10_37236_8903,
author = {Hooman R. Dehkordi and Graham Farr},
title = {On the strong {Hanani-Tutte} theorem},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {1},
doi = {10.37236/8903},
zbl = {1471.05024},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8903/}
}
TY - JOUR
AU - Hooman R. Dehkordi
AU - Graham Farr
TI - On the strong Hanani-Tutte theorem
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/8903/
DO - 10.37236/8903
ID - 10_37236_8903
ER -
%0 Journal Article
%A Hooman R. Dehkordi
%A Graham Farr
%T On the strong Hanani-Tutte theorem
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8903/
%R 10.37236/8903
%F 10_37236_8903
Hooman R. Dehkordi; Graham Farr. On the strong Hanani-Tutte theorem. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/8903
