Hanani-Tutte for Radial Planarity II

[摘要] A drawing of a graph $G$, possibly with multiple edges but without loops, is radial if all edges are drawn radially, that is, each edge intersects every circle centered at the origin 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 distances of the vertices from the origin respect the 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 if a leveled graph $G$ has a radial drawing in which every two independent edges cross an even number of times, then $G$ is radial planar. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.

[学科分类] 统计和概率