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.
Search WWH ::




Custom Search