Radial Level Planarity Testing and Embedding in Linear Time (Extended Abstract)

Bachmaier, Christian and Brandenburg, Franz J. and Forster, Michael (2004) Radial Level Planarity Testing and Embedding in Linear Time (Extended Abstract). In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 393-405(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_37).

Full text not available from this repository.


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 [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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_37
Classifications: G Algorithms and Complexity > G.490 Embeddings
P Styles > P.660 Radial
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/469

Actions (login required)

View Item View Item