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

Upward Drawings: A directed acyclic graph has an upward planar drawing if
it has a planar straight-line drawing such that for any directed edge v

w the
y -coordinate of v is smaller than the y -coordinate of w . Testing whether a graph
has an upward planar drawing is NP-hard [9]. There exists a way to formulate
“ G has an upward planar drawing” as either IP or as a Satisfiability-problem,
using partial orders on the edges and vertices [5]. The transformations in this
paper give a different way of testing this via IP:

ₒ

Lemma 3. A directed acyclic graph has an upward planar drawing if and only if
it has a planar bar-visibility representation where for all edges the head is above
the tail.

Proof. Any straight-line upward planar drawing can be transformed into a flat
visibility representation using Thm. 5 and 6. Since y -coordinates are unchanged,
any edge is necessarily drawn vertical with the head above the tail, so this is a
bar-visibility representation. Vice versa, given such a bar-visibility representa-
tion, it can be transformed into a y -monotone poly-line drawing (Thm. 4) and
from there into a straight-line drawing (Thm. 1). Since y -coordinates and left-
to-right-orders are preserved this gives an upward planar drawing.

w must be above the tail” as
constraints in the IP for bar-visibility representations defined in [4]. Therefore:

It is easy to express“theheadofedge v ₒ

Corollary 4. There exists an integer program with O ( n 3 ) variables and con-
straints to test whether a planar graph has an upward planar drawing. Moreover,
the same integer program also finds the minimum-height upward planar drawing.

7Con lu on

This paper considered transformations of one type of planar drawings into an-
other without increasing the height. In particular planar straight-line drawings
are equivalent with respect to the height to flat visibility representations or
y -monotone poly-line drawing, while they are more powerful than either orthog-
onal drawings or poly-line drawings. The latter two drawing styles are again
equivalent with respect to drawing height.
The main gap left open concerns visibility representations. Is it possible to
transform any visibility representation into a flat visibility representation of the
same height?
As for future problems, it would be interesting to study other drawing ob-
jectives, and whether they can be preserved while changing the layout style.
Hoffman et al. [11] recently gave some worst-case ratios, but for other graph
drawing styles. Is it possible to transform any y -monotone poly-line drawing
into a straight-line drawing of the same area? The example in Thm. 2 makes
this unlikely, but can it be transformed into a straight-line drawing of asymp-
totically the same area?