Some properties of k-Delaunay and k-Gabriel graphs

DOI10.1016/J.COMGEO.2012.04.006MaRDI QIDQ691765zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• On structural and graph theoretic properties of higher order Delaunay graphs
• Convex hulls and metric Gabriel graphs
• Hamiltonicity for convex shape Delaunay and Gabriel graphs
• Hamiltonicity for convex shape Delaunay and Gabriel graphs
• Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
• Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties
• On geometric constructions of \((k,g)\)-graphs
• scientific article; zbMATH DE number 3877217
• scientific article; zbMATH DE number 500365
• scientific article; zbMATH DE number 4085714

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Lower Bound for the Number of Vertices of a Graph
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Classes of graphs which approximate the complete Euclidean graph
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Covering and coloring problems for relatives of intervals
• Delaunay graphs are almost as good as complete graphs
• Geometric Thickness of Complete Graphs
• Higher order Delaunay triangulations
• Improved upper bound on the stretch factor of Delaunay triangulations
• On circles containing the maximum number of points
• On crossing numbers of geometric proximity graphs
• On structural and graph theoretic properties of higher order Delaunay graphs
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• On the chromatic number of some geometric type Kneser graphs
• On the number of higher order Delaunay triangulations
• Optimization for first order Delaunay triangulations
• Routing with guaranteed delivery in ad hoc wireless networks
• Some extremal results on circles containing points
• Structural tolerance and Delaunay triangulation
• Testing bipartiteness of geometric intersection graphs

Cited in

(13)

• Matchings in higher-order Gabriel graphs
• scientific article; zbMATH DE number 2086250 (Why is no real title available?)
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• Proximity structures for geometric graphs
• Coloring certain proximity graphs
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• On the edge crossing properties of Euclidean minimum weight Laman graphs
• On structural and graph theoretic properties of higher order Delaunay graphs
• Quantitative classification of vortical flows based on topological features using graph matching
• 3-coloring arrangements of line segments with 4 slopes is hard
• 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
• Hamiltonicity for convex shape Delaunay and Gabriel graphs

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

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