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. The main intuition behind this result is that Gabriel triangulations are increasing-chord graphs, a fact which might be of independent interest. 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.

Dehkordi, H.R., Frati, F., & Gudmundsson, J. (2015). Increasing-Chord Graphs On Point Sets. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 19(2), 761-778 [10.7155/jgaa.00348].

Increasing-Chord Graphs On Point Sets

FRATI, FABRIZIO;
2015

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. The main intuition behind this result is that Gabriel triangulations are increasing-chord graphs, a fact which might be of independent interest. 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.
Dehkordi, H.R., Frati, F., & Gudmundsson, J. (2015). Increasing-Chord Graphs On Point Sets. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 19(2), 761-778 [10.7155/jgaa.00348].
File in questo prodotto:
File Dimensione Formato  
Published.pdf

accesso aperto

Descrizione: Published version at https://doi.org/10.7155/jgaa.00348
Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 471.66 kB
Formato Adobe PDF
471.66 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/286679
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? ND
social impact