Information Technology Reference
In-Depth Information
Lemma 2.
Any visibility representation of a connected graph has width at most
max
{
m, n
}
after deleting redundant columns.
+
b
,where
b
is the number of local minima and maxima of polygonal curves in the
poly-line drawing, since all other pseudo-vertices are eliminated when removing
zig-zags.
Hence for Thm. 6 the width is max
{
m, n
}
. For Thm. 5 it is at most max
{
n,m
}
5B x-D awingsMadeF t
Theorem 7.
Any planar orthogonal drawing ʓ can be transformed into a planar
flat orthogonal drawing ʓ
of the same height.
Proof.
For any vertex
v
,let
r
be a row that intersects the box
B
(
v
) representing
v
and set
B
(
v
):=
B
(
v
)
r
. Any edge that attached vertically at
B
(
v
)canbe
extended to end at
B
(
v
) instead. Any edge that attached at
B
(
v
) horizontally
in row
r
also attaches at
B
(
v
). Any edge
e
that attached at
B
(
v
) horizontally,
but not in row
r
, is re-routed by inserting a bend where
e
attached at
B
(
v
),
and then going vertically towards
B
(
v
). Now vertical edge segments at
v
may
overlap, but this can easily be remedied by replacing the leftmost and rightmost
column of
B
(
v
)bysu
cientlymanycolumns.SeeFig.5.
∩
Fig. 5.
Transforming orthogonal drawings into flat orthogonal drawings
Thm. 7 does not generally preserve
y
-monotonicity, and this is unavoidable.
Theorem 8.
The planar graph in Fig. 6 has a y-monotone orthogonal drawing
on 6 rows, but it has no planar y-monotone flat orthogonal drawing on 6 rows,
and also no planar visibility representation on 6 rows.
2-grids force vertices
v,w
onto row 5 and
v
,w
onto row
Proof.
(Sketch) The 4
×
v
,w
,c
}
enclose
x
and
x
, respectively, which
2. The two cycles
{
v,w,c
}
and
{
forces
c
to span both rows 3 and 4.
One transformation remains to be studied: Can every visibility representation
be turned into a flat visibility representation? A variation of Thm. 7 shows that
this is possible for bipartite graphs.
Corollary 3.
Any planar visibility representation of a bipartite graph G can be
transformed into a planar flat visibility representation of the same height.