# Radial Level Planarity Testing and Embedding in Linear Time

Christian Bachmaier, Franz J. Brandenburg, Michael Forster

January, 2004
Graph Drawing### Abstract

Every planar graph has a concentric representation based on a breadth first
search, see [21]. 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 is 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–18] and show that radial planarity is decidable
in linear time, and that a radial planar embedding can be computed in linear
time.

Publication

Giuseppe Liotta (ed.),
*Proc. Graph Drawing, GD 2003*,
Lecture Notes in Computer Science 2919:393–405
Springer