On the strong Hanani-Tutte Theorem

Hooman R. Dehkordi, Graham Farr

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article numberP1.43
Number of pages16
JournalElectronic Journal of Combinatorics
Volume28
Issue number1
DOIs
Publication statusPublished - 26 Feb 2021

Cite this