Discrete Applied Mathematics Seminar by Michael Pelsmajer: The Strong Hanani-Tutte Theorem for Radial Planarity

Speaker: Michael Pelsmajer, Illinois Institute of Technology 

Title: The Strong Hanani-Tutte Theorem for Radial Planarity

Abstract: Graph drawing considers various ways to represent a network visually. In a radial drawing, each edge is a "radial" plane curve, meaning that any circle centered at the origin intersects the edge at most once. Furthermore, if the vertices of the graph are ordered (or partitioned into levels) then their distances from the origin must respect the ordering (or leveling).

A pair of edges is even (odd) if the two edges cross an even (odd) number of times; a pair of edges is adjacent if the two edges share an endpoint. The Strong Hanani-Theorem states that if a graph is drawn such that non-adjacent pairs of edges are even, then the graph can be embedded without crossings.

We prove the Strong Hanani-Tutte Theorem for radial drawings, which yields a simple algorithm for radial planarity testing. This is joint work with Rado Fulek and Marcus Schaefer. 

 

Discrete Applied Math Seminar

Request Zoom link