Practical Level Planarity Testing and Layout with Embedding Constraints

Harrigan, Martin and Healy, Patrick (2008) Practical Level Planarity Testing and Layout with Embedding Constraints. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 62-68 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_9).

Full text not available from this repository.

Abstract

We describe a practical method to test a leveled graph for level planarity and provide a level planar layout of the graph if the test succeeds, all in quadratic running-time. Embedding constraints restricting the order of incident edges around the vertices are allowed.

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

Repository Staff Only: item control page

References

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A Linear Algorithm for Embedding Planar Graphs using PQ-Trees. Journal of Comp. and Sys. Sci., 30(1):54-76, 1985.

G. Di Battista and E. Nardelli. Hierarchies and Planarity Theory. IEEE Trans. Sys., Man and Cybern., 18(6):1035-1046, 1988.

C. Gutwenger, K. Klein, and P. Mutzel. Planarity testing and Optimal Edge Insertion with Embedding Constraints. In GD'06, pages 126-137. Springer, 2007.

P. Healy and A. Kuusik. Algorithms for Multi-Level Graph Planarity Testing and Layout. Theor. Comp. Sci., 320(2-3):331-344, 2004.

L. Heath and S. Pemmaraju. Recognizing Leveled-PLanar DAGs in Linear Time. In GD'95, pages 300-311, Springer, 1995.

M. Jünger and S. Leipert. Level Planar Embedding in Linear Time. Journal of Graph Alg. and App., 6(1):67-113, 2002.

B. Randerath, E. Speckenmeyer, E. Boros, P. Hammer, A. Kogan, K. Makino, B. Simeone, and O. Cepek. A Satisfiability Formulation of Problems on Level Graphs. Technical report 40-2001, Rutgers center for Operations Research, Rutgers University, 2001.