Planarities and Hanani-Tutte

The beautiful (and old) Hanani-Tutte theorem states that a graph is planar if and only if it can be drawn so that any pair of independent edges crosses an even number of times. One of the many results which witness that planarity of a graph is well-understood. However, many variants of planarity have been defined for applications: there are c-planarity, simultaneous planarity, strip-planarity, level-planarity, radial planarity, and the list doesn't end here. Most of these planarity variants we do not yet understand very well, theoretically or practically (algorithmically). In this talk we review if and how the Hanani-Tutte characterization of planarity can shed new light on planarity variants. Hanani-Tutte style characterizations are very algebraic and lend themselves to implementations. This leads to an algorithm that can solve many (if not all) of the planarity problems mentioned above.

Event Topic

Discrete Applied Math Seminar