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 , pp. 219-229(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item