Information Technology Reference
In-Depth Information
so have area 56 and 100, respectively. Then note that if
n
≥
9 the disjoint union
of
K
8
and
n
−
8 isolated vertices has area at least (
n
−
8 + 10)
2
, greater than
the area of
E
n
.
Theorem 3.
AtreeT with leaves has representation height
/
2
or
/
2
+1
.
Further, if T has no vertices of degree 2 then T has representation height
/
2
exactly.
We prove Theorem 3 by converting a rectangle visibility representation of a
tree
T
into an orienting path cover of
T
.An
orienting path cover
of
T
is a set
of directed paths in
T
containing all of its vertices, such that whenever two paths
share an edge, they point the same direction. We prove the following lemmas:
Lemma 1.
A tree has a representation with height k if and only if it has an
orienting path cover with k paths.
Lemma 2.
Atreewith leaves has an orienting path cover with at most
/
2
+1
paths.
Note that every orienting path cover must include a path ending at every
leaf. This is at least
paths. So equivalently, Lemma 2 says that
T
has an
orienting path cover using at most one extra path. We find a family of examples
for which this extra path is necessary.
/
2
References
1. Dean, A.M., Hutchinson, J.P.: Rectangle-visibility representations of bipartite
graphs. Discrete Appl. Math. 75(1), 9-25 (1997)
2. Kant, G., Liotta, G., Tamassia, R., Tollis, I.G.: Area requirement of visibility rep-
resentations of trees. Inform. Process. Lett. 62(2), 81-88 (1997)
