Cyclic Level Planarity Testing and Embedding

Bachmaier, Christian and Brunner, Wolfgang and König, Christof (2008) Cyclic Level Planarity Testing and Embedding. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 50-61 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_8).

Full text not available from this repository.

Abstract

In this paper we introduce cyclic level planar graphs, which are a planar version of the recurrent hierarchies from Sugiyama et al. [8] and the cyclic extension of level planar graphs, where the first level is the successor of the last level. We study the testing and embedding problem and solve it for strongly connected graphs in time $O(|V| log |V|)$.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_8
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:828

Repository Staff Only: item control page

References

C. Bachmaier, F. J. Brandenburg, and M. Forster. Radial level planarity testing and embedding in linear time. Journal of Graph Algorithms and Applications, 9(1):53-97, 2005.

J. Boyer and W. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241-273, 2004.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

P. Healy and A Kuusik. Algorithms for multi-level graph planarity testing and layout. Theoretical Computer Science, 320(2-3):331-344, 2004.

J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549-568, 1974.

M. Jünger and S. Leipert. Level planar embedding in linear time. Journal of Graph Algorithms and Applications, 6(1):67-113, 2002.

M. Kaufmann and D. Wagner. Drawing Graphs, volume 2025 of LNCS. Springer, 2001.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109-125, 1981.