Logo

Login

Practical Level Planarity Testing and Layout with Embedding Constraints

Harrigan, Martin and Healy, Patrick (2008) Practical Level Planarity Testing and Layout with Embedding Constraints. [Conference Paper]

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
Classifications:M Methods > M.500 Layered
P Styles > P.480 Layered
ID Code:860
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=62

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.