Information Technology Reference
In-Depth Information
Height-Preserving Transformations
of Planar Graph Drawings
Therese Biedl
David R. Cheriton School of Computer Science, University of Waterloo,
Waterloo, ON N2L 3G1, Canada
biedl@uwaterloo.ca
Abstract.
There are numerous styles of planar graph drawings, such
as straight-line drawings, poly-line drawings, orthogonal graph draw-
ings and visibility representations. Given a planar drawing in one of
these styles, can it be converted it to another style while keeping the
height unchanged? This paper answers this question for (nearly) all pairs
of these styles, as well as for related styles that additionally restrict
edges to be
y
-monotone and/or vertices to be horizontal line segments.
These transformations can be used to develop new graph drawing results,
especially for height-optimal drawings.
Keywords:
Planar graph drawing, poly-line drawing, straight-line draw-
ing, orthogonal drawing, visibility representation, minimizing height.
1 Introduction
Let
G
=(
V,E
) be a simple graph with
n
=
edges.
All graphs in this paper are
planar
, i.e., can be drawn without crossings. Some
of the most commonly used drawings styles are the following: (1) A
straight-
line drawing
is a drawing where vertices are points and edges are straight-line
segments between their endpoints. Any planar graph has a planar straight-line
drawing in an
O
(
n
)
|
V
|
vertices and
m
=
|
E
|
O
(
n
)-grid [8][17]. (2) A
poly-line drawing
(called
mixed
model
in [12]) is a drawing where vertices are points and edges are polygonal
curves. Some results exist for poly-line drawings for which no equivalent straight-
line drawing result is known; for example Kant gave drawings in an
O
(
n
)
×
O
(
n
)-
grid with large minimum angle [12]. (3) A (2-directional)
visibility representation
is a drawing where vertices are axis-aligned boxes and edges are horizontal or
vertical line segments. Every planar graph has a visibility representation in an
O
(
n
)
×O
(
n
)-grid [16][20][21]. (4) An
orthogonal (box-)drawing
is a drawing where
all vertices are axis-aligned boxes and edges are polygonals curves for which all
line segments are horizontal or vertical. Every planar graph has an orthogonal
drawing in an
O
(
n
)
×
×
O
(
n
)-grid [18].
Supported by NSERC and the Ross and Muriel Cheriton Fellowship. The author
would like to thank the referees of a preliminary version for helpful comments, and
Fabrizio Frati and Geza Toth for pointing out reference [15].
