Increasing-Chord Graphs On Point Sets

Dehkordi, Hooman Reisi and Frati, Fabrizio and Gudmundsson, Joachim (2014) Increasing-Chord Graphs On Point Sets. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 464-475 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_39).

Full text not available from this repository.

Abstract

We tackle the problem of constructing increasing-chord graphs spanning 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 logn) edges (and with no Steiner points) spanning P.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_39
Classifications:G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.250 Geometry
ID Code:1455

Repository Staff Only: item control page

References

Aichholzer, O., Aurenhammer, F., Icking, C., Klein, R., Langetepe, E., Rote, G. (2001) Generalized self-approaching curves. Discr. Appl. Math. 109: pp. 3-24

Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V. Self-approaching graphs. In: Didimo, W., Patrignani, M. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 260-271

Bern, M.W., Eppstein, D., Gilbert, J.R. (1994) Provably good mesh generation. J. Comput. Syst. Sci. 48: pp. 384-409

Berg, M., Cheong, O., Kreveld, M., Overmars, M. (2008) Computational Geometry: Algorithms and Applications. Springer, Heidelberg

Di Battista, G., Vismara, L. (1996) Angles of planar triangular graphs. SIAM J. Discrete Math. 9: pp. 349-359

Dillencourt, M.B., Smith, W.D. (1996) Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Mathematics 161: pp. 63-77

Eades, P., Whitesides, S. (1996) The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica 16: pp. 60-82

Gabriel, K.R., Sokal, R.R. (1969) A new statistical approach to geographic variation analysis. Systematic Biology 18: pp. 259-278

Icking, C., Klein, R., Langetepe, E. (1999) Self-approaching curves. Math. Proc. Camb. Phil. Soc. 125: pp. 441-453

Liotta, G.: Chapter 4 of Handbook of Graph Drawing. CRC Press (2014); Tamassia, R. (ed.)

Matula, D.W., Sokal, R.R. (1980) Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane. Geographical Analysis 12: pp. 205-222

Monma, C.L., Suri, S. (1992) Transitions in geometric minimum spanning trees. Discrete & Computational Geometry 8: pp. 265-293

Papadimitriou, C.H., Ratajczak, D. (2005) On a conjecture related to geometric routing. Theoretical Computer Science 344: pp. 3-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)

Rote, G. (1994) Curves with increasing chords. Math. Proc. Camb. Phil. Soc. 115: pp. 1-12