Information Technology Reference
In-Depth Information
On Self-Approaching and Increasing-Chord Drawings
of 3-Connected Planar Graphs
Martin N ollenburg,RomanPrutkin, and Ignaz Rutter
Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
Abstract.
An
st
-pathinadrawing of a graph is self-approaching if during a
traversal of the corresponding curve from
s
to any point
t
on the curve the dis-
tance to
t
is non-increasing. A path has increasing chords if it is self-approaching
in both directions. A drawing is self-approaching (increasing-chord) if any pair
of vertices is connected by a self-approaching (increasing-chord) path.
We study self-approaching and increasing-chord drawingsoftriangulations and
3-connected planar graphs. We show that in the Euclidean plane, triangulations
admit increasing-chord drawings, and for planar 3-trees we can ensure planarity.
Moreover, we give a binary cactus that does not admit a self-approaching drawing.
Finally, we show that 3-connected planar graphs admit increasing-chord drawings
in the hyperbolic plane and characterize the trees that admit such drawings.
1
Introduction
Finding a path between two vertices is one of the most fundamental tasks users want
to solve when consideringgraph drawings. Empirical studies have shown that users
perform better in path-finding tasks if the drawings exhibit a stronggeodesic-path ten-
dency [10, 17]. Not surprisingly, graph drawings in which a path with certain properties
exists between every pair of vertices have become a popular research topic. Over the
last years a number of different drawing conventions implementing the notion of strong
geodesic-path tendency have been suggested, namely
greedy drawings
[18],
(strongly)
monotonedrawings
[2], and
self-approaching
and
increasing-chord drawings
[1]. Note
that throughout this paper, all drawings are straight-line and vertices are mapped to
distinct points.
The notion of greedy drawings came first and was introduced by Rao et al. [18].
Motivated by greedy routing schemes, e.g., for sensor networks, one seeks a drawing,
where for every pair of vertices
s
and
t
there exists an
st
-path, along which the dis-
tances to
t
decrease in every vertex. This ensures that greedily sending a messageto
a vertex that is closer to the destination guarantees delivery. Papadimitriou and Rata-
jczak conjectured that every 3-connected planar graph admits a greedy embedding into
the Euclidean plane [16]. This conjecture has been proved independently by Leighton
and Moitra [13] and Angelini et al. [5]. Kleinberg [12] showed that every connected
graph has a greedy drawing in the hyperbolic plane. Eppstein and Goodrich [7] showed
how to construct such an embedding, in which the coordinates of each vertex are repre-
sented using only
O
(log
n
) bits, and Goodrich and Strash [9] provided a corresponding
succinct
representation for greedy embeddings of 3-connected planar graphs in
2
.An-
gelini et al. [3] showed that some graphs require exponential area for a greedy drawing
R
