Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs

DOI10.1016/j.comgeo.2012.04.006zbMath1254.05042OpenAlexW2171133375MaRDI QIDQ691765

Stefan Langerman, Sébastien Collette, Ferran Hurtado, Prosenjit Bose, Maria Saumell, Vera Sacristán, Matias Korman

Publication date: 4 December 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.04.006

zbMATH Keywords

geometric graphsproximity graphs

Mathematics Subject Classification ID

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

Related Items (6)

3-coloring arrangements of line segments with 4 slopes is hard ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ Higher-order triangular-distance Delaunay graphs: graph-theoretical properties ⋮ Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs ⋮ Quantitative classification of vortical flows based on topological features using graph matching ⋮ Matchings in higher-order Gabriel graphs

Cites Work

• On the number of higher order Delaunay triangulations
• Delaunay graphs are almost as good as complete graphs
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• On crossing numbers of geometric proximity graphs
• Covering and coloring problems for relatives of intervals
• Some extremal results on circles containing points
• Classes of graphs which approximate the complete Euclidean graph
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Structural tolerance and Delaunay triangulation
• Higher order Delaunay triangulations
• On circles containing the maximum number of points
• Optimization for first order Delaunay triangulations
• On the chromatic number of some geometric type Kneser graphs
• ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• Geometric Thickness of Complete Graphs
• Improved upper bound on the stretch factor of delaunay triangulations
• A Lower Bound for the Number of Vertices of a Graph
• Routing with guaranteed delivery in ad hoc wireless networks
• Unnamed Item
• Unnamed Item

This page was built for publication: Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs