## Radial Level Planarity Testing and Embedding in Linear Time (Extended Abstract)
Bachmaier, Christian and Brandenburg, Franz J. and Forster, Michael
(2004)
Full text not available from this repository. ## AbstractEvery 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 [18,17,15,16,12,13] and show that radial planarity is decidable in linear time, and that a radial planar embedding can be computed in linear time.
Repository Staff Only: item control page References |