Information Technology Reference
In-Depth Information
(unbounded) polygonal regions, then we call the original drawing a
convex drawing
.
If every region is
strictly convex
(that is, all interior angles are strictly less than
ˀ
), we
also call the drawing
strictly convex
. Note that a convex drawing is also monotone [4,2],
but a monotone drawing is not necessarily convex. Strict convexity forbids vertices of
degree 2. In this paper, when we talk about(strongly) monotone drawings, this always
includes the planarity requirement. Otherwise, as Angelini et al. [2] observed, drawing
any spanning tree of the given graph in a (strongly) monotone way and inserting the
remaining edges would yield a (strongly) monotone drawing.
PreviousWork.
While any 3-connected plane graph has a greedy drawing in the Eu-
clidean plane [10] (even without crossing [7]), this is, unfortunately, not true for trees.
Nollenburg and Prutkin [11] gave a complete characterization for the tree case, which
shows that no tree with a vertex of degree 6 or more admits a greedy drawing.Alam-
dari et al. [1] have studied a subclass of greedy drawings, so-called
self-approaching
drawings
which require that there always is a source-target path such that the distance
decreases for any triplet of intermediate points on the
edges
, not only for the vertices.
Carlson and Eppstein [6] study convex drawings of trees. They give linear-time algo-
rithms that optimize the angular resolution of the drawings, both for the fixed- and the
variable-embedding case. They observe that convexity allows them to pick edgelengths
arbitrarily, withoutintroducing crossings.
For monotone drawings, Angelini et al. [2] studied the variable-embedding case.
They showed that any
n
-vertex tree admits a straight-line monotone drawing on a grid of
size
O
(
n
1
.
6
)
O
(
n
2
) (using a DFS-
based algorithm). They also showed that any biconnected planar graph has a monotone
drawing (using exponential area). Further, they observed that not every planar graph
admits a monotone drawing if its embedding is fixed. They introduced the concept
of
strong monotonicity
and showed that there is a drawing of a planar triangulation
that is not strongly monotone. Hossain and Rahman [9] improve some of the results
of Angelini et al. by showing that every connected planar graph admits a monotone
drawing of size
O
(
n
)
×O
(
n
2
) and that such a drawing can be computed in linear time.
Both the BFS- and the DFS-based algorithms of Angelini et al. precompute a set of
O
(
n
1
.
6
) (using a BFS-based algorithm) or
O
(
n
)
×
×
n
1 vectors in decreasing order of slope. For this, they use two different partial traver-
sals of the so-called Stern-Brocot tree, an infinite tree whose vertices are in bijection
with the irreducible positive rational numbers. Such numbers can be seen as
primitive
vectors in 2d, that is, as vectors with pairwise different slopes. Then both algorithms do
a depth-first (pre-order) traversal of the input tree. Whenever they hit a new edge, they
assign to it the steepest unused vector. They place the root of the input tree at the origin
and draw each edge (
u,v
) by adding the vector assigned to (
u,v
) to the position of
u
.
They call such tree drawings
slope-disjoint
.Wewon't formally define this notion here,
but it is not hard to see that it implies monotonicity.
Angelini, with a different set of co-authors [3], investigated the fixed-embedding
case. They showed that, on the
O
(
n
)
−
O
(
n
2
) grid, every connected plane graph admits a
monotone drawing with two bends per edgeandanyouterplane graph admits a straight-
line monotone drawing.
×
