Height-Preserving Transformations of Planar Graph Drawings - Graph Drawing - page 387

6

v w

5

4

x c

x

3

w v

2

1

Fig. 6. A graph that has an orthogonal y -monotone on 6 rows, but not if vertices must
be horizontal segments or edges have no bends

Proof. Since G is bipartite, it has a vertex-coloring with 2 colors. Proceed as
in Thm. 7, but use the topmost row intersecting B ( v ) for each vertex v in one
color-class, and the bottommost row for each vertex in the other color-class. Each
vertical edge remains vertical. Each horizontal edge becomes y -monotone since
it connects two differently-colored vertices. So the result is a flat y -monotone
orthogonal drawing, which can be converted into a flat visibility representation
by Thm. 6.

It remains open whether visibility representations of arbitrary graphs can also
be made flat without increasing the height.

6 Applications

This section highlights some applications of the above results.
Best Drawing Styles for Lower Bounds and Algorithms: Whenever
possible, lower bounds for the height of planar graph drawings should be done
for poly-line drawings or for orthogonal drawings: by the above transformations
such a lower bound then also holds for visibility representations and straight-line
drawings. Vice versa, algorithms to create planar graph drawings of small height
should ideally be for straight-line drawings; they then also hold for all other
models. Alternative, algorithms could be given for flat visibility representations;
the same height-bound then also holds for straight-line drawings and all other
models, though the width does not transfer.
Drawings of Small Height: Two examples of using height-transformations
to achieve new results shall suce:

Theorem 9. Every outer-planar graph G has a planar straight-line drawing of
height O ( pw ( G )) , which is in O (log n ) .Herepw ( G ) is the so-called pathwidth
of the graph. 3

Proof. Every outer-planar graph can be made 2-connected while increasing the
pathwidth by at most a constant factor [1]. Every 2-connected outer-planar graph
has a flat visibility representation of height O ( pw ( G )) [2]. This flat visibility
representation is a flat y -monotone orthogonal drawing, which by Thms. 4 and
1 can be turned into a straight-line drawing of the same height.

3 A similar result was claimed in [2], but required the (incorrect) transformation in
that paper.