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
    0 references
    0 references
    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
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references