Every planar graph has a concentric representation based on a breadth first search, see [23]. The vertices are placed on concentric circles and the edges are routed as curves without crossings. Here we take the opposite view. A graph with a given partitioning of its vertices onto k concentric circles is k-radial planar, if the edges can be routed monotonic between the circles without crossings. Radial planarity ia a generalisation of level planarity, where the vertices are placed on k horizontal lines. We extend the technique for level planarity testing of [12, 13, 15-17, 19] and show that radial planarity is decidable in linear time, and that a radial planar embedding can be computed in linear time.
Nathalie Vollstaedt