topological graph theory In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in ...

, the Hanani–Tutte theorem is a result on the parity of edge crossings in a

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

. 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)..

History

The result is named after

Haim Hanani Haim Hanani ( as Chaim Chojnacki– 8 April 1991) was a Polish-born Israeli mathematician, known for his contributions to combinatorial design theory, in particular for the theory of pairwise balanced designs and for the proof of an existenc ...

, who proved in 1934 that every drawing of the two minimal non-planar graphs ''K''₅ and ''K''_3,3 has a pair of edges with an odd number of crossings, and after

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...

, who stated the full theorem explicitly in 1970. A parallel development of similar ideas in

algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...

has been credited to

Egbert van Kampen Egbert Rudolf van Kampen (28 May 1908 – 11 February 1942) was a Dutch mathematician. He made important contributions to topology, especially to the study of fundamental groups. Life Van Kampen was born to Dutch parents in Belgium, wher ...

Arnold S. Shapiro Arnold Samuel Shapiro (1921, Boston, Massachusetts – 1962, Newton, Massachusetts) was an American mathematician known for his eversion of the sphere and Shapiro's lemma. He also was the author of an article on Clifford algebras and periodicit ...

, and

Wu Wenjun Wu Wenjun ( zh, s=吴文俊; 12 May 1919 – 7 May 2017), also commonly known as Wu Wen-tsün, was a Chinese mathematician, historian, and writer. He was an academician at the Chinese Academy of Sciences (CAS), best known for the Wu's method of ...

Applications

One consequence of the theorem is that testing whether a graph is planar may be formulated as solving a

system of linear equations In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables. For example, :\begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of three ...

over the finite field of order two. These equations may be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, but the resulting

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

s 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, known for the

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do ...

as well as for the Euclidean plane, 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. 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 drawing In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each edge ...

s, drawings minimizing the number of uncrossed edges, and

clustered planarity In graph drawing, a clustered planar graph is a graph together with a hierarchical clustering on its vertices, such that the graph drawn together with a collection of simple closed curves surrounding each cluster, so that there are no crossings be ...

References

{{DEFAULTSORT:Hanani-Tutte theorem Planar graphs Graph drawing