Hanani-Tutte for radial planarity. II (Q2684882)

Summary: 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. For Part I see [the authors, J. Graph Algorithms Appl. 21, No. 1, 135--154 (2017; Zbl 1358.05277)].