Increasing-Chord Graphs On Point Sets

Dehkordi, Hooman Reisi and Frati, Fabrizio and Gudmundsson, Joachim (2014) Increasing-Chord Graphs On Point Sets. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 464-475(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_39).

Full text not available from this repository.

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. 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_39
Classifications: G Algorithms and Complexity > G.560 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.250 Geometry
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 May 2015 14:49
Last Modified: 21 May 2015 14:49
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1455

Actions (login required)

View Item View Item