Area Requirements for Drawing Hierarchically Planar Graphs

Lin, Xuemin and Eades, Peter (1998) Area Requirements for Drawing Hierarchically Planar Graphs. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 219-229 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_64).

Full text not available from this repository.

Abstract

In this paper, we investigate area requirements for drawing s-t hierarchically planar graphs by straight-lines. Two drawing standards will be discussed: 1) each vertex is represented by a point and 2) grid visibilty representation (that is, a line segment is allowed to represent a vertex). For the first drawing standard, we show an exponential area lower bound needed for drawing hierarchically planar graphs. The lower bound holds even for hierarchical graphs without transitive arcs, in contrast to the results for upward planar drawing. Applications of some existing algorithms from upward drawing can guarantee the quadratic drawing area for grid visibility representation but do not necessarily guarantee the minimum drawing area. Motivated by this, we will present another grid visibility drawing algorithm which is efficient and guarantees the minimum drawing area.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_64
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.480 Layered
P Styles > P.540 Planar
ID Code:81

Repository Staff Only: item control page

References

J.A. Bondy and U.S.R. Murty, Graph Theory with Application, The Macmilan Press LTD, 1977.

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis, Algorithms for Automatic Graph Drawing: An Annotated Bibliography, Computational Geometry: Theory and Application, 4, 235-282, 1994.

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

G. Di Battista and R. Tamassia, Algorithms for Plane Representations of Acyclic Diagraphs, Theoretical Computer Science, 61, 175-198, 1988.

G. Di Battista and R. Tamassia, On-line Planarity Testing, SIAM Journal on Computing, 25(5), 1996.

G. Di Battista, R. Tamassia, and I.G. Tollis, Area Requirement and Symmetry Display of Planar Upward Drawings, Discrete & Computational Geometry, 7(381-401), 1992.

P. Eades, Q. Feng and X. Lin, Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs, Graph Drawing '96, LNCS 1190, Springer-Verlag, 113-128, 1996.

P. Eades, X. Lin, and R. Tamassia, An Algorithm for Drawing a Hierarchical Graph, International Journal of Computational Geometry and Applications, 6(2), 145-155, 1996.

A. Garg and R. Tamassia, On the Computational Complexity of Upward and Rectilinear Planarity Testing, Graph Drawing '94, LNCS, Springer-Verlag, 286-297, 1995.

L.S. Heath and S.V. Pemmaraju, Recognizing Leveled-Planar Dags in Linear Time, Graph Drawing '95, LNCS 1027, Springer-Verlag, 1995.

X. Lin, Analysis of Algorithms for Drawing Graphs, PHD thesis, University of Queensland, 1992.

X. Lin and P. Eades, Area Requirement for Drawing Hierarchically Planar Graphs, Tec. Rep., The University of Western Australia, 1997.