Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
From MaRDI portal
Publication:691765
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
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
