2016/08/30 by Radoslav Fulek, Michael J. Pelsmajer, Fulek, Radoslav +4
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Search Problems #cs.CG
paper · pdf · doi:10.48550/arxiv.1608.08662
Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
arxiv created 2016/08/30 · openalex publication_date 2016/08/30 · arxiv updated 2016/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, …, Ck 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.