Hanani–Tutte theorem
{{Short description|On parity of crossings in graph drawings}}
In topological graph theory, the Hanani–Tutte theorem is a result on the parity of edge crossings in a graph drawing. It states that every drawing in the plane of a non-planar graph contains a pair of independent edges (not both sharing an endpoint) that cross each other an odd number of times. Equivalently, it can be phrased as a planarity criterion: a graph is planar if and only if it has a drawing in which every pair of independent edges crosses evenly (or not at all).{{citation
| last = Schaefer | first = Marcus
| doi = 10.7155/jgaa.00298
| issue = 4
| journal = Journal of Graph Algorithms and Applications
| mr = 3094190
| pages = 367–440
| title = Toward a theory of planarity: Hanani–Tutte and planarity variants
| volume = 17
| year = 2013| doi-access = free
}}.
History
The result is named after Haim Hanani, who proved in 1934 that every drawing of the two minimal non-planar graphs K5 and K3,3 has a pair of edges with an odd number of crossings,{{citation
| last = Chojnacki | first = Ch.
| issue = 1
| journal = Fundamenta Mathematicae
| pages = 135–142
| title = Über wesentlich unplättbare Kurven im dreidimensionalen Raume
| url = http://eudml.org/doc/212715
| volume = 23
| year = 1934| doi = 10.4064/fm-23-1-135-142
| doi-access = free
}}. See in particular (1), p. 137. and after W. T. Tutte, who stated the full theorem explicitly in 1970.{{citation
| last = Tutte | first = W. T. | authorlink = W. T. Tutte
| journal = Journal of Combinatorial Theory
| mr = 0262110
| pages = 45–53
| title = Toward a theory of crossing numbers
| volume = 8
| year = 1970
| doi=10.1016/s0021-9800(70)80007-2| doi-access =
}}. A parallel development of similar ideas in algebraic topology has been credited to Egbert van Kampen, Arnold S. Shapiro, and Wu Wenjun.{{citation
| last = Levow | first = Roy B.
| contribution = On Tutte's algebraic approach to the theory of crossing numbers
| mr = 0354426
| pages = 315–314
| publisher = Florida Atlantic Univ., Boca Raton, Fla.
| title = Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972)
| year = 1972}}.{{citation
| last = Schaefer | first = Marcus
| editor1-last = Bárány | editor1-first = I.
| editor2-last = Böröczky | editor2-first = K. J.
| editor3-last = Tóth | editor3-first = G. F.
|display-editors = 3 | editor4-last = Pach | editor4-first = J.
| contribution = Hanani–Tutte and related results
| location = Berlin
| publisher = Springer
| series = Bolyai Society Mathematical Studies
| title = Geometry—Intuitive, Discrete, and Convex—A Tribute to László Fejes Tóth
| url = http://ovid.cs.depaul.edu/documents/htsurvey.pdf}}{{citation
| last = van Kampen | first = E. R. | authorlink = Egbert van Kampen
| doi = 10.1007/BF02940628
| issue = 1
| journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
| mr = 3069580
| pages = 72–78
| title = Komplexe in euklidischen Räumen
| volume = 9
| year = 1933| s2cid = 121909529 }}.{{citation
| last = Wu | first = Wen-Tsün | authorlink = Wu Wenjun
| journal = Acta Mathematica Sinica
| mr = 0076334
| pages = 505–552
| title = On the realization of complexes in Euclidean spaces. I
| volume = 5
| year = 1955}}.{{citation
| last = Shapiro | first = Arnold | authorlink = Arnold S. Shapiro
| journal = Annals of Mathematics
| mr = 0089410
| pages = 256–269
| series = Second Series
| title = Obstructions to the imbedding of a complex in a Euclidean space. I. The first obstruction
| volume = 66
| issue = 2 | year = 1957
| doi=10.2307/1969998| jstor = 1969998 }}.{{citation
| last = Wu | first = Wen Jun | authorlink = Wu Wenjun
| issue = 4
| journal = Journal of Systems Science and Mathematical Sciences
| mr = 818118
| pages = 290–302
| title = On the planar imbedding of linear graphs. I
| volume = 5
| year = 1985}}. Continued in [http://www.sysmath.com/jweb_xtkxysx/CN/article/showTenYearOldVolumn.do 6 (1): 23–35, 1986].
Applications
One consequence of the theorem is that testing whether a graph is planar may be formulated as solving a system of linear equations over the finite field of order two. These equations may be solved in polynomial time, but the resulting algorithms are less efficient than other known planarity tests.
Generalizations
For other surfaces S than the plane, a graph can be drawn on S without crossings if and only if it can be drawn in such a way that all pairs of edges cross an even number of times; this is known as the weak Hanani–Tutte theorem for S. The strong Hanani–Tutte theorem states that a graph can be drawn without crossings on S if and only if it can be drawn in such a way that all independent pairs of edges cross an even number of times, without regard for the number of crossings between edges that share an endpoint;{{citation
| last1 = Pelsmajer | first1 = Michael J.
| last2 = Schaefer | first2 = Marcus
| last3 = Stasi | first3 = Despina
| doi = 10.1137/08072485X
| issue = 3
| journal = SIAM Journal on Discrete Mathematics
| mr = 2538654
| pages = 1317–1323
| title = Strong Hanani–Tutte on the projective plane
| volume = 23
| year = 2009| citeseerx = 10.1.1.217.7182}}.
this strong version does not hold for all surfaces,{{citation |arxiv=1709.00508 |doi=10.1007/s00493-019-3905-7 |title=Counterexample to an extension of the Hanani–Tutte theorem on the surface of genus 4 |date=2019 |last1=Fulek |first1=Radoslav |last2=Kynčl |first2=Jan |journal=Combinatorica |volume=39 |issue=6 |pages=1267–1279 }} but it is known to hold for
the plane, the projective plane and the torus.{{citation
| last1 = Fulek | first1 = Radoslav
| last2 = Pelsmajer | first2 = Michael J.
| last3 = Schaefer | first3 = Marcus
| editor1-last = Buchin | editor1-first = Kevin
| editor2-last = Colin de Verdière | editor2-first = Éric
| arxiv = 2009.01683
| contribution = Strong Hanani–Tutte for the torus
| doi = 10.4230/LIPIcs.SoCG.2021.38
| pages = 38:1–38:15
| publisher = Schloss Dagstuhl – Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 37th International Symposium on Computational Geometry, SoCG 2021, June 7–11, 2021, Buffalo, NY, USA (Virtual Conference)
| volume = 189
| year = 2021| doi-access = free
}}
The same approach, in which one shows that pairs of edges with an even number of crossings can be disregarded or eliminated in some type of graph drawing and uses this fact to set up a system of linear equations describing the existence of a drawing, has been applied to several other graph drawing problems, including upward planar drawings,{{citation
| last1 = Fulek | first1 = Radoslav
| last2 = Pelsmajer | first2 = Michael J.
| last3 = Schaefer | first3 = Marcus
| last4 = Štefanković | first4 = Daniel
| editor-last = Pach | editor-first = János | editor-link = János Pach
| contribution = Hanani–Tutte, monotone drawings, and level-planarity
| isbn = 978-1-4614-0110-0
| publisher = Springer
| title = Thirty essays on geometric graph theory
| year = 2013}}. drawings minimizing the number of uncrossed edges,{{citation
| last1 = Pach | first1 = János | author1-link = János Pach
| last2 = Tóth | first2 = Géza
| doi = 10.1006/jctb.2000.1978
| issue = 2
| journal = Journal of Combinatorial Theory
| mr = 1794693
| pages = 225–246
| series = Series B
| title = Which crossing number is it anyway?
| volume = 80
| year = 2000| doi-access = free
}}.{{citation
| last1 = Pelsmajer | first1 = Michael J.
| last2 = Schaefer | first2 = Marcus
| last3 = Štefankovič | first3 = Daniel
| doi = 10.1016/j.jctb.2006.08.001
| issue = 4
| journal = Journal of Combinatorial Theory
| mr = 2325793
| pages = 489–500
| series = Series B
| title = Removing even crossings
| volume = 97
| year = 2007| doi-access =
}}. and clustered planarity.{{citation
| last1 = Gutwenger | first1 = C.
| last2 = Mutzel | first2 = P. | author2-link = Petra Mutzel
| last3 = Schaefer | first3 = M.
| contribution = Practical experience with Hanani–Tutte for testing c-planarity
| doi = 10.1137/1.9781611973198.9
| pages = 86–97
| title = 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)| date = 2014
| isbn = 978-1-61197-319-8
}}.