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.
Search WWH ::




Custom Search