Information Technology Reference
In-Depth Information
Repeating this for all zig-zags removes all horizontal segments with non-
integer coordinates and hence gives the desired height and a flat visibility rep-
resentation of the graph with pseudo-vertices. Any pseudo-vertex can now be
removed and replaced by a bend or line-segment, if needed, to give an orthogo-
nal drawing that satisfies all conditions.
A very similar construction converts
y
-monotone flat orthogonal drawings into
flat visibility representations.
Theorem 6.
Any planar flat y-monotone orthogonal drawing ʓ can be trans-
formed into a planar flat visibility representation ʓ
of the same height that
preserves y-coordinates and left-to-right orders.
Proof.
Assume that there exists an edge
e
in
ʓ
that attaches horizontally at one
endpoint
v
and has bends. Since
ʓ
is flat,
v
is a horizontal segment, which can
expand until it covers the bend of
e
nearest to
v
.Afterwards
e
attaches vertically
at
v
. Repeat this until all edges with bends attach vertically at both endpoints.
If there are now no bends then the claim holds. Otherwise, let
e
be an edge
with bends; by the above it attaches vertically at both its endpoints. Since
e
is drawn
y
-monotone, it attaches at the top of one endpoint and the bottom of
the other endpoint, and inbetween must have a zig-zag. As before (see Fig. 4)
such a zig-zag can be removed by shifting parts of the drawing rightwards. This
does not add height or bends. Applying this to all edges that have bends gives
a planar visibility representation.
One height-transformation among point drawings and flat drawings remains to
be studied: Can flat orthogonal drawings be made
y
-monotone without increasing
theheight?Theanswerhereis“no”sincethegraphofThm.3hasapoly-line
drawing on 6 rows, hence also (by Thm. 5) a flat orthogonal drawing on 6 rows,
but it has no
y
-monotone orthogonal drawing, much less one that is flat.
Summary:
Combining all the above results yields that straight-line draw-
ings,
y
-monotone poly-line drawings,
y
-monotone flat orthogonal drawings and
flat visibility representations are equivalent with respect to the height of planar
drawings.
2
Poly-line drawings and flat orthogonal drawings are also equivalent,
and the former group sometimes requires strictly more height than the latter.
Width Considerations:
For Thm. 1 the width may have to increase exponen-
tially (Thm. 3). For Thm. 4 the width did not increase. For Thm. 5 and 6 the
width may increase, but after eliminating all zig-zags many columns are
redun-
dant
: They contain no vertical edge, nor are they the only column of a vertex.
In an orthogonal drawing redundant columns can simply be deleted. One can
easily show the following:
2
Historical note: At WAOA'12 [2], I claimed that any flat visibility representation
can be transformed into a straight-line drawing of the same height directly, without
using [15]. Unfortunately the transformation in [2] is incorrect since the resulting
drawing may not be planar; details are in the full version.
