Information Technology Reference
In-Depth Information
increase the width. Now within each row
r
enumerate the vertices and pseudo-
vertices as
w
1
,...,w
k
from left to right, and assign
w
i
to the point (
r, i
); clearly
this preserves
y
-coordinates and left-to-right-orders. Since
w
1
,...,w
k
had integer
x
-coordinates before, the
x
-coordinate of each can only decrease. Due to the
pseudo-vertices edge-segments connect vertices in the same or two adjacent rows,
so they can be drawn without crossings. Replacing the pseudo-vertices by bends
gives the desired poly-line drawing
ʓ
. The claim on height and
y
-monotonicity
holds since
y
-coordinates and left-to-right-orders are preserved.
Theorem 5.
Any planar poly-line drawing ʓ can be transformed into a planar
flat orthogonal drawing ʓ
of the same height that preserves y-coordinates and
left-to-right orders. If ʓ is y-monotone, then so is ʓ
.
Proof.
Insert pseudo-vertices at bends and whenever a segment of an edge crosses
a row, temporarily allowing non-integer
x
-coordinates. Now within each row
r
enumerate the vertices and pseudo-vertices as
w
1
,...,w
k
from left to right. In
ʓ
, replace each
w
i
by a box of width max
1
,
deg
up
(
w
i
)
,
deg
down
(
w
i
)
,where
deg
up
(
w
i
) and deg
down
(
w
i
) are the number of neighbours above and below
w
i
,
respectively. Place these boxes in row
r
in the same left-to-right order.
If an edge was drawn horizontally in
ʓ
, then draw it horizontally in
ʓ
as well.
Each non-horizontal edge ends in two adjacent rows due to the pseudo-vertices.
Connect the edges between two adjacent rows using VLSI channel routing (see
e.g. [13]), using two bends per edge and lots of new rows with non-integer
y
-
coordinates that contain horizontal edge segments and nothing else.
{
}
x
l
move
rig
htward by
x
r
− x
l
x
r
Fig. 4.
Replace bends and row-crossings by pseudo-vertices (white). Replace points by
boxes and route non-horizontal segments as zig-zags. Then remove zig-zags by shifting
parts of the drawing rightward.
Each non-horizontal edge is now routed as a “zig-zag”, ending vertically at
its endpoints. It is well known (see e.g. [3]) that such a zig-zag can be removed
as follows: Let [
x
l
,x
r
]
y
s
by the horizontal segment of a zig-zag. Let
M
be all
bends and endpoints of vertices with
x
-coordinate exceeding
x
r
,or
y
-coordinate
at least
y
s
and
x
-coordinate at least
x
l
. Then move all points in
M
rightwards,
i.e., add
x
r
−x
l
to their
x
-coordinate. See also Fig. 4. Notice that this preserves
y
-coordinates and planarity, and eliminates the horizontal segment.
×
