Hanani-Tutte for Radial Planarity II

Abstract

A drawing of a graph $G$ is radial if the vertices of $G$ are placed on concentric circles $C_1,\dots ,C_k$ with common center $c$, and edges are drawn radially: every edge intersects every circle centered at $c$ at most once. $G$ is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of $G$ are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges $e$ and $f$ in a graph is independent if $e$ and $f$ do not share a vertex. We show that a graph $G$ is radial planar if $G$ has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.

Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)