Increasing-Chord Graphs On Point Sets - Graph Drawing - page 466

a Gabriel triangulation if the Gabriel graph of P is a triangulation. A triangulation is a
Gabriel triangulation if and only if every angle of a triangle delimiting an internal face
is acute [8]. See [8,10,11] for more properties about Gabriel graphs.
In Section 3 we will prove that every Gabriel triangulation is increasing-chord. A
weaker version of the converse is also true, as proved in the following.

Lemma 2. Let P be a setofpoints andlet G ( P,S ) be an increasing-chord graph
spanning P .Thenall theedges of the Gabriel graph of P are in S .

Proof. Suppose, for a contradiction, that there exists an increasing-chord graph
G ( P,S ) andanedge uv of the Gabriel graph of P such that uv ∈ S . Then, con-
sider any increasing-chord path

P =( u = w 1 ,w 2 ,...,w k = v ) in G .Since uv ∈ S ,it
follows that k> 2.Assume w.l.o.g.that w 1 , w 2 ,and w k appear in this clockwise order
on the boundary of triangle ( w 1 ,w 2 ,w k ). Since the closed disk with diameter uv does
not contain any point in its interior or on its boundary, it follows that w k w 2 w 1 < 90 ⓦ . ∠

90 ⓦ ,then If ∠ w 2 w 1 w k ≥ | w 1 w k | < | w 2 w k | , a contradiction to the assumption that

w 2 w 1 w k < 90 ⓦ , then the altitude of triangle ( w 1 ,w 2 ,w k )
incident to w k hits w 1 w 2 in a point h . Hence,

P is increasing-chord. If ∠

| hw k | < | w 2 w k | , a contradiction to the

assumption that P is increasing-chord which proves the lemma.

3 Planar Increasing-Chord Graphs with Few Steiner Points

We show that, for any point set P , one can construct an increasing-chord planar graph
G ( P ,S ) such that P ↆ P and | P |∈ O ( | P |

).Ourresult has two ingredients. The first
one is that Gabriel triangulations are increasing-chord graphs. The second one is a result
of Bern et al. [3] stating that, for any point set P , there exists a point set P such that
P ↆ P ,

|P |∈O ( |P| ),and P admits a Gabriel triangulation. Combining these two
facts proves our main result. The proof that Gabriel triangulations are increasing-chord
graphs consists of two parts. In the first one, we prove that geometric graphs having a
ʸ -path between every pair of points are increasing-chord. In the second one, we prove
that in every Gabriel triangulation there exists a ʸ -path between every pair of points.
We introduce some definitions. The slope of a straight-line segment uv is the angle
spanned by a clockwise rotation around u that brings uv to coincide with the positive
x -axis. Thus, if ʸ is the slope of uv ,then ʸ + k 360 ⓦ is also the slope of uv , · ∀ k ∈ Z .

45 ⓦ ; ʸ +45 ⓦ ]. Astraight-line segment uv is a ʸ -edge if its slope is in the interval [ ʸ −

Also, a geometric path P =( p 1 ,...,p k ) is a ʸ -path from p 1 to p k if p i p i +1 is a ʸ -edge,

for every 1 ≤ i ≤ k − 1. Consider a point a on a ʸ -path P from p 1 to p k . Then, the

subpath from a to p k is also a ʸ -path. Moreover, denote by W ʸ ( a ) the closed

wedge with an angle of 90 ⓦ incident to a and whose delimiting lines have slope ʸ

P a of P

45 ⓦ −

and ʸ +45 ⓦ ;then P a is contained in W ʸ ( a ) (see Fig. 2). We have the following:

Lemma 3. Let P be a ʸ -path from p 1 to p k .Then, P is increasing-chord.

with end-points
p and q is self-approaching from p to q if and only if, for every point a on

Proof. Lemma 3 in [9] states the following (see also [1]): A curve C

,there
exists a closed wedge with an angle of 90 ⓦ incident to a and containing the part of

C

C