Information Technology Reference
In-Depth Information
Increasing-Chord Graphs On Point Sets
Hooman Reisi Dehkordi
1
, Fabrizio Frati
2
, and Joachim Gudmundsson
2
1
School of Information Technologies, Monash University, Australia
hooman.dehkordi@monash.edu
2
School of Information Technologies, The University of Sydney, Australia
{
fabrizio.frati,joachim.gudmundsson
}
@sydney.edu.au
Abstract.
We tackle the problem of constructing increasing-chord graphs span-
ning point sets. We prove that, for every point set
P
with
n
points, there exists an
increasing-chord planar graph with
O
(
n
) Steiner points spanning
P
.Further, we
prove that, for every convex point set
P
with
n
points, there exists an increasing-
chord graph with
O
(
n
log
n
) edges (and with no Steiner points) spanning
P
.
1
Introduction
A
proximitygraph
is a geometric graph that can be constructed from a point set by
connecting points that are “close”, for some local or global definition of proximity.
Proximity graphs constitute a topic of research in which the areas of graph drawing
and computational geometry nicely intersect. A typical graph drawing question in this
topic asks to characterize the graphs that can be represented as a certain type of prox-
imity graphs. A typical computational geometry question asks to designanalgorithm
to construct a proximity graph spanning a given point set.
Euclidean minimum spanning trees and Delaunay triangulations are famousexam-
ples of proximity graphs. Given a point set
P
,a
Euclidean minimum spanning tree
(MST) of
P
is a geometric tree with
P
as vertex set and with minimum total edgelength;
the
Delaunay triangulation
of
P
is a triangulation
T
such that no point in
P
lies inside
the circumcircle of any triangle of
T
.Fromacomputational geometry perspective, given
a point set
P
with
n
points, an MST of
P
with maximumdegree five exists [12] and can
be constructed in
O
(
n
log
n
) time [4]; also, the Delaunay triangulation of
P
exists and
can be constructed in
O
(
n
log
n
) time [4]. From a graph drawing perspective, every tree
with maximumdegree five admits a representationasanMST[12]anditisNP-hard to
decide whether a tree with maximumdegree six admits such a representation [7]; also,
characterizing the class of graphs that can be represented as Delaunay triangulations is
a deeply studied question, which still eludes a clear answer; see, e.g., [5,6]. Refer to the
excellent survey by Liotta [10] for more on proximity graphs.
While proximity graphs have constituted a frequent topic of research in graph draw-
ing and computational geometry, they gained a sudden peak in popularity even outside
these communities in 2004, when Papadimitriou
et al.
[14] devised an elegant routing
protocol that works effectively in all the networks that can be represented as a certain
type of proximity graphs, called
greedygraphs
. For two points
p
and
q
in the plane,
Work partially supported by the Australian Research Council (grant DE140100708).
