Remember Me
Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:

OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Dehkordi, Hooman Reisi; Frati, Fabrizio; Gudmundsson, Joachim (2014)
Languages: English
Types: Preprint
Subjects: Computer Science - Computational Geometry, Computer Science - Discrete Mathematics

Classified by OpenAIRE into

arxiv: Computer Science::Sound
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 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)
    • 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) (1980) 205-222
    • 12. Monma, C.L., Suri, S.: Transitions in geometric minimum spanning trees. Discrete & Computational Geometry 8 (1992) 265-293
    • 13. Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theoretical Computer Science 344(1) (2005) 3-14
    • 14. Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In Johnson, D., Joseph, A., Vaidya, N., eds.: MOBICOM '03. (2003) 96-108
    • 15. Rote, G.: Curves with increasing chords. Math. Proc. Camb. Phil. Soc. 115(1) (1994) 1-12
  • No related research data.
  • No similar publications.

Share - Bookmark

Funded by projects

  • ARC | Discovery Early Career Rese...

Cite this article

Collected from

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok