Information Technology Reference
In-Depth Information
2
.Wang and He [21] used a custom distance metric to construct planar, convex
and succinct greedy embeddings of 3-connected planar graphs using Schnyder realiz-
ers [20]. Nollenburg and Prutkin [14] characterized trees admitting aEuclidean greedy
embedding.However,anumber of interesting questions remain open, e.g., whether ev-
ery 3-connected planar graph admits a planar and convex Euclidean greedy embedding
(strongPapadimitriou-Ratajczak conjecture [16]). Regarding planar greedy drawingsof
triangulations, the only known result is an existential proof by Dhandapani [6].
While getting closer to the destination, a greedy path can make numerousturns and
may even look like a spiral, which hardly matches the intuitive notion of geodesic-path
tendency. To overcome this, Angelini et al. [2] introduced monotone drawings, where
one requires that for every pair of vertices
s
and
t
there exists a
monotonepath
, i.e., a
path that is monotone with respect to some direction. Ideally, the monotonicity direction
should be
#
st
. This property is called
strong monotonicity
.Angelini et al. showed that
biconnected planar graphs admit monotone drawings [2] and that plane graphs admit
monotone drawings with few bends [4]. The existence of strongly monotone planar
drawings remains open, even for triangulations.
Both greedy and monotone paths may have arbitrarily large
detour
, i.e., the ratio of
the path length and the distance of the endpoints can, in general, not be bounded by
a constant. Motivated by this fact, Alamdari et al. [1] recently initiated the study of
self-approaching
graph drawings. Self-approaching curves, introduced by Icking [11],
are curves where for any point
t
on the curve, the distance to
t
decreases continuously
while traversing the curve from the start to
t
.Equivalently, a curve is self-approaching
if, for any three points
a
,
b
,
c
in this order along the curve, it is dist(
a, c
)
R
in
dist(
b,c
),
where dist denotes the Euclidean distance. An even stricter requirement are so-called
increasing-chord
curves, which are curves that are self-approaching in both directions.
The name is motivated by the characterization of such curves, which states that a curve
has increasing chords if and only if for any four distinct points
a,b,c,d
in that order,
it is dist(
b,c
)
≤
≥
dist(
a, d
). Self-approaching curves have detour at most 5.333 [11]
and increasing-chord curves have detour at most 2.094 [19]. Alamdari et al. [1] studied
the problem of recognizing whether a given graph drawing is self-approaching as well
as connectinggiven points to a self-approaching drawing.Theyalsogave a complete
characterization of trees admitting self-approaching drawings.
We note that every increasing chord drawing is self-approaching and strongly mono-
tone [1]. The converse is not true. A self-approaching drawing is greedy, but not
necesserily monotone, and a greedy drawing is generally neither self-approaching nor
monotone. For trees, the notions of self-approaching and increasing-chord drawing co-
incide.
Contribution.
We obtain the following results on constructing self-approaching or
increasing-chord drawings.
1. We show that every triangulation has an increasing-chord drawing (answering an
open question of Alamdari et al. [1]) and construct a
binary cactus
that does not admit
a self-approaching drawing (Sect. 3). The latter is a notable difference to greedy draw-
ings since both constructions of greedy drawings for 3-connected planar graphs [5, 13]
essentially show that every binary cactushasagreedy drawing.