Information Technology Reference
In-Depth Information
On Monotone Drawings of Trees
Philipp Kindermann
1
, Andr´eSchulz
2
, Joachim Spoerhase
1
, and Alexander Wolff
1
1
Lehrstuhl f ur Informatik I, Universitat W urzburg,Germany
http://www1.informatik.uni-wuerzburg.de/en/staff
2
Institutfur Mathematische Logik und Grundlagenforschung,Universitat Munster, Germany
andre.schulz@uni-muenster.de
Abstract.
A crossing-free straight-line drawing of a graph is
monotone
if there
is a monotone path between any pair of vertices with respect to
some
direction.
We show how to construct a monotone drawing ofatreewith
n
vertices on an
O
(
n
1
.
5
)
×O
(
n
1
.
5
) grid whose angles are close to the best possible angular reso-
lution. Ourdrawingsare
convex
,thatis,ifeveryedge to a leaf is substituted by a
ray, the (unbounded) faces form convex regions. It is known that convex drawings
are monotone and, in the case of trees, also crossing-free.
A monotone drawing is
stronglymonotone
if, for every pair of vertices, the
direction that witnesses the monotonicity comes from the vector that connects the
two vertices. We show that every tree admits a strongly monotone drawing.For
biconnected outerplanar graphs, this is easy to see. On the other hand, we present
a simply-connected graph that does not have a strongly monotone drawing in any
embedding.
1
Introduction
Anatural requirement for the layout of a connected graph is that between any source
vertex and any target vertex, there should be a source-target path that approaches the
target according to some distance measure. A large body of literature deals with prob-
lems of this type; various measures have been studied. For example, in a
greedy drawing
it is possible to decide locally where to go, by selecting in the current vertex any neigh-
bor closer to the target. In a
monotone
drawing, the distance between vertices (on the
desired source-target path) is measured with respect to their projections on
some
line,
which may be different for any source-target pair. In
stronglymonotone
drawings, that
line is always the line from source to target, and in
upward
drawings, the line is always
the vertical line, directed upwards.
In this paper, we focus on monotone and strongly monotone drawings of trees with
additional aesthetic properties such as convexity or small area. Given a tree, we call the
edges incident to the leaves
leafedges
and all other edges
interior edges
. We direct all
edges away from the root. Given a straight-line drawing of a tree, we substitute each
leaf edge by a ray whose initial part coincides with the edge. The embedding of the
tree defines a combinatorial embedding of the tree, that is the order of the edges around
every vertex. The faces are then specified by this combinatorial embedding as leaf-to-
leaf paths. If the faces of the augmented drawing are realized as convex nonoverlapping
This research was supported by the ESF EuroGIGA project GraDR (DFG grant Wo 758/5-1).
