Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Twenty-second International Symposium on Graph Drawing, GD 2014
DOI: 10.7155/jgaa.00348
Increasing-Chord Graphs On Point Sets
Vol. 19, no. 2, pp. 761-778, 2015. Regular paper.
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.
Submitted: October 2014.
Reviewed: February 2015.
Revised: February 2015.
Accepted: February 2015.
Final: February 2015.
Published: November 2015.
Communicated by Christian Duncan and Antonios Symvonis
article (PDF)
BibTeX