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, Perugia, Italy , pp. 393-405 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_37).

Full text not available from this repository.

Abstract

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
ID Code:469

Repository Staff Only: item control page

References

C. Bachmaier, F. J. Brandenburg, and M. Foster. Radial level planarity testing and embedding in linear time. Technical Report MIP-0303, University of Passau, June 2003.

C. Bachmaier and M. Raitner. Improved symmetric lists. Submitted for publication, May 2003.

K. S. Booth and G. S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Science, 13:335-379, 1976.

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences, 30:54-76, 1985.

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

G. Di Battista, P. Eades, R. Tamassia, and I.C. Tollis. Graph drawing: Algorithms for Visualization of Graphs. Prentice Hall, 1999.

G. Di Battista and E. Nardelli. Hierarchies and planarity theory. IEEE Transactions on Systems, Man, and Cybernetics, 18(6):1035-1046, 1988.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, 1996.

V. Dujmovic, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McGartin, N. Nishimura, P. Ragde, F. Rosamond, M. Suderman, S. Whitesides, and D. R. Wood. On the parameterized complexity of layered graph drawing. In F. Meyer auf der Heide, editor, Proc. European Symposium on Algorithms, ESA 2001, volume 2161 of LNCS, pages 488-499. Springer, 2001.

S. Even. Algorithms, chapter 7, pages 148-191. Computer Science Press, 1979.

GTL. Graph Template Library. http://www.infosun.fmi.uni-passau.de/GTL/. University of Passau.

L. S. Heath and S. V. Pemmaraju. Recognizing leveled-planar dags in linear time. In Proc. Graph Drawing '95, volume 1027 of LNCS, pages 300-311. Springer, 1996.

L. S. Heath and S. V. Pemmaraju. Stack and queue layouts of directed acyclic graphs: Part II. SIAM Journal on Computing, 28(5):1588-1626, 1999.

L. S. Heath and A. L. Rosenberg. Laying out graphs using queues. SIAM Journal on Computing, 21(5):927-958, 1992.

M. Jünger and S. Leipert. Level planar embedding in linear time. In Proc. Graph Drawing '99, volume 1731 of LNCS, pages 72-81. Springer, 1999.

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

M. Jünger, S. Leipert, and P. Mutzel. Level planarity testing in linear time. In Proc. Graph Drawing '98, volume 1547 of LNCS, pages 224-237. Springer, 1998.

S. Leipert. Level Planarity Testing and Embedding in Linear Time. Dissertation, Mathematisch-Naturwissenschaftliche Fakultät der Universität zu Köln, 1988.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In P. Rosenstiehl, editor, Theory of Graphs, International Symposium, Rome, July 1966, pages 215-232. Gordon and Breanch, 1967.

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.

J. D. Ullman. Computational Aspects of VLSI, chapter 3.5, pages 111-114. Computer Science Press, 1984.