Information Technology Reference
In-Depth Information
The main difficulty seems to lie in the construction of planar increasing-chord graphs
spanning sets of points lying on the boundary of an acute triangle.
Gabriel graphs naturally generalize to higher dimensions, where empty balls replace
empty disks. In Section 3 we showed that, for points in
2
, every Gabriel triangulation
is increasing-chord. Can this result be generalized to higher dimensions?
R
d
,anyGabrieltriangulation of
P
is
Problem 2.
Is it true that, for every point set
P
in
R
increasing-chord?
Finally, it would be interesting to understand if increasing-chord graphs with few
edges can be constructed for any (possibly non-convex) point set:
Problem 3.
Is it true that, for every point set
P
, there exists an increasing-chord graph
G
(
P,S
) with
2
)?
|
S
|∈
o
(
|
P
|
References
1. Aichholzer, O., Aurenhammer, F., Icking, C., Klein, R., Langetepe, E., Rote, G.: Generalized
self-approaching curves. Discr. Appl. Math. 109(1-2), 3-24 (2001)
2. Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V.: Self-approachinggraphs. In:
Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 260-271. Springer, Hei-
delberg (2013)
3. Bern, M.W., Eppstein, D., Gilbert, J.R.: Provably good mesh generation. J. Comput. Syst.
Sci. 48(3), 384-409 (1994)
4. de Berg,M.,Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algo-
rithms and Applications, 3rd edn. Springer, Heidelberg (2008)
5. Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3),
349-359 (1996)
6. Dillencourt, M.B., Smith, W.D.: Graph-theoretical conditions for inscribability and Delaunay
realizability. Discrete Mathematics 161(1-3), 63-77 (1996)
7. Eades, P., Whitesides, S.: The realization problem for Euclidean minimum spanning trees is
NP-hard. Algorithmica 16(1), 60-82 (1996)
8. Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Sys-
tematic Biology 18, 259-278 (1969)
9. Icking,C.,Klein,R.,Langetepe, E.: Self-approaching curves. Math. Proc. Camb. Phil.
Soc. 125(3), 441-453 (1999)
10. Liotta, G.: Chapter 4 of Handbook of Graph Drawing. CRC Press (2014); Tamassia, R. (ed.)
11. Matula, D.W., Sokal, R.R.: Properties of Gabriel graphs relevant to geographic variation
research and clustering of points in the plane. Geographical Analysis 12(3), 205-222 (1980)
12. Monma, C.L., Suri, S.: Transitions in geometric minimum spanning trees. Discrete & Com-
putational Geometry 8, 265-293 (1992)
13. Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoretical
Computer Science 344(1), 3-14 (2005)
14. Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location
information. In: Johnson, D., Joseph, A., Vaidya, N. (eds.) MOBICOM 2003, pp. 96-108
(2003)
15. Rote, G.: Curves with increasing chords. Math. Proc. Camb. Phil. Soc. 115(1), 1-12 (1994)
