Increasing-chord graphs on point sets

DOI10.1007/978-3-662-45803-7_39MaRDI QIDQ5892033zbMATH OpenOpenAlexFDO

Authors Hooman Reisi Dehkordi, Fabrizio Frati, Joachim Gudmundsson

Publication date 7 January 2015

Published in Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2592

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Recommendations

• Increasing-chord graphs on point sets
• (Weakly) self-approaching geometric graphs and spanners
• On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• On the number of plane geometric graphs

Cited in

(6)

• Self-approaching paths in simple polygons
• On Self-Approaching and Increasing-Chord Drawings of 3-Connected Planar Graphs
• On self-approaching and increasing-chord drawings of 3-connected planar graphs
• Curves with increasing chords
• Increasing-chord graphs on point sets
• Angle-monotonicity of Delaunay triangulation

This page was built for publication: Increasing-chord graphs on point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5892033)