Information Technology Reference
In-Depth Information
Representation of vertices
points
horizontal segments
boxes
Cor.3
?
straight-line
drawing
visibility
representation
flat visibility
representation
[15]
Thm.6
Thm.8
Thm.8
Thm.4
y
-monotone
poly-line drawing
flat
y
-mon.
orth. drawing
y
-monotone
orth. drawing
Thm.5
Cor.2
Thm.3
Thm.3
Thm.7
Thm.4
poly-line
drawing
orthogonal
drawing
flat orth.
drawing
Thm.5
trivial implication
non-trivial transformation
transformation not always possible
transformation possible for bipartite graphs,
?
existence unknown in general
Fig. 1.
Summary of height-preserving transformations
to have
width w
and
height h
if (possibly after translation) vertices and bends are
placed on the [1
,w
]
[1
,h
]-grid. The height is thus measured by the number of
rows
, i.e., horizontal lines with integer
y
-coordinates that intersect the drawing.
1
Drawings in this paper are required to be grid-drawings, with some exceptions
for ease of description that will be pointed out as they occur.
The goal is to transform a planar drawing
ʓ
into a different planar drawing
ʓ
which has the same height but uses a different drawing style. If
ʓ
and
ʓ
are
both flat, then these transformations will have two useful properties as follows.
ʓ
preserves y-coordinates
if any vertex has the same
y
-coordinate in
ʓ
and
ʓ
. This is well-defined since both drawings are flat.
ʓ
preserves left-to-right-
orders
if, scanning each row from left to right, one encounters the same edges
and vertices, in the same order, in both
ʓ
and
ʓ
. One can easily show that if
ʓ
is planar and
ʓ
preserves
y
-coordinates and left-to-right-orders, then
ʓ
is also
planar and has the same height. Furthermore,
ʓ
is
y
-monotone if
ʓ
was.
×
3Poin -D awings
This section considers transformations among drawing styles that represent ver-
tices by points. One of the few existing results about height-preserving transfor-
mationsisbyPachandToth:
Theorem 1.
[15] Any planar y-monotone poly-line drawing ʓ can be trans-
formed into a planar straight-line drawing ʓ
with the same height.
1
In the pictures vertex representations are thickened for ease of readability, but this
is not counted towards the height; e.g. the drawings in Fig. 1 have height 3.
