Hanani-Tutte for radial planarity. II (Q2684882)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Hanani-Tutte for radial planarity. II |
scientific article |
Statements
Hanani-Tutte for radial planarity. II (English)
0 references
17 February 2023
0 references
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)].
0 references
radial planar graphs
0 references
crossing-free radial drawing
0 references
0 references