Increasing-Chord Graphs On Point Sets

Authors

  • Hooman Dehkordi
  • Fabrizio Frati
  • Joachim Gudmundsson

DOI:

https://doi.org/10.7155/jgaa.00348

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 logn) edges (and with no Steiner points) spanning P.

Downloads

Download data is not yet available.

Downloads

Published

2015-11-01

How to Cite

Dehkordi, H., Frati, F., & Gudmundsson, J. (2015). Increasing-Chord Graphs On Point Sets. Journal of Graph Algorithms and Applications, 19(2), 761–778. https://doi.org/10.7155/jgaa.00348