Increasing-Chord Graphs On Point Sets

Preprint English OPEN
Dehkordi, Hooman Reisi ; Frati, Fabrizio ; Gudmundsson, Joachim (2014)
  • Subject: Computer Science - Computational Geometry | Computer Science - Discrete Mathematics
    arxiv: Computer Science::Sound
    acm: MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY

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 log n) edges (and with no Steiner points) spanning P.
  • References (15)
    15 references, page 1 of 2

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

    2. Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V.: Self-approaching graphs. In Didimo, W., Patrignani, M., eds.: GD '12. Volume 7704 of LNCS. (2013) 260-271

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

    4. de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. 3rd edn. Springer, Heidelberg (2008)

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

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

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

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

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

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

  • Metrics
    No metrics available
Share - Bookmark