Information Technology Reference
In-Depth Information
Theorem 10.
Any 4-connected planar graph has a planar flat visibility repre-
sentation of height at most
n/
2
.
Proof.
Any 4-connected planar graph has a straight-line drawing where the sum
of the width and height is at most
n
[14]. After possible rotation, the height is at
most
, and with Thms. 5 and 6 one obtains a flat visibility representation
of height at most
n/
2
n/
2
.
The best previous bound on the height of visibility representations of 4-
connected planar graphs was
3
n
[10].
Simplified Proofs:
Some results are known about graphs that have planar
straight-line drawings of height
h
. In particular, any such graph has pathwidth
at most
h
[7], and there exists an algorithm that is fixed-parameter tractable in
h
to test whether a graph has a straight-line drawing of height at most
h
[6]. By the
results in this paper a graph has a straight-line drawing of height
h
if and only
if it has a flat visibility representation of height
h
. While “simplicity of proof” is
a subjective matter, in my opinion the presentation of both of the above results
can be simplified if one shows the properties for flat visibility representations of
height
h
, rather than straight-line drawings.
HH-drawings:
In a previous paper [19] we studied
HH-drawings
,wherea
planar graph
G
with a vertex partition
V
=
A
4
B
should be drawn such that all
vertices in
A
have positive
y
-coordinates and all vertices in
B
have negative
y
-
coordinates. We gave a condition that is necessary for straight-line HH-drawings
and sucient for
y
-monotone poly-line HH-drawings. By the result by Pach and
Toth (Thm. 1) the condition is hence necessary and sucient for straight-line
HH-drawings. This proves:
∪
Theorem 11.
Any planar bipartite graph has a planar straight-line HH-drawing.
Testing whether a planar graph with a given partition has a planar straight-line
HH-drawing can be done in linear time.
Minimizing Heights Using Integer Programs:
In a recent paper, we devel-
oped integer program (IP) formulations for many graph drawing problems where
vertices and edges are represented by axis-aligned boxes [4]. In particular, we
gave an integer program with
O
(
hn
2
) variables and constraints to test whether
a graph has a
bar-visibility representation
(i.e., a visibility representation where
vertices are horizontal segments and all edges are vertical) that has height
h
.It
is not hard to modify this IP so that horizontal edges are allowed as well; then it
tests the existence of flat visibility representations of height
h
. Since straight-line
drawings and flat visibility representations are equivalent with respect to height,
therefore:
Theorem 12.
There exists an integer program with O
(
hn
2
)
variables and con-
straints to test whether a graph has a planar straight-line drawing of height h.
While an algorithm was already known to test whether
G
has a planar drawing
of height at most
h
[6], its rather large run-time of
O
(2
32
h
3
poly(
n
)) means that
solving the above integer program might well be faster in practice.
