ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS

DOI10.1142/S0218195909003143zbMath1209.05199MaRDI QIDQ3405973

Prosenjit Bose, Manuel Abellanas, Jesús García-López, Carlos M. Nicolás, Ferran Hurtado, Pedro A. Ramos

Publication date: 12 February 2010

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

geometric graphsDelaunay graphhigher order proximity graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Structural characterization of families of graphs (05C75)

Related Items

PROXIMITY GRAPHS: E, δ, Δ, χ AND ω, Flip graphs of bounded degree triangulations, Coloring planar homothets and three-dimensional hypergraphs, Decomposition of multiple coverings into more parts, Higher-order triangular-distance Delaunay graphs: graph-theoretical properties, On crossing numbers of geometric proximity graphs, Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs, On the number of higher order Delaunay triangulations, Hamiltonicity for convex shape Delaunay and Gabriel graphs, Bottleneck matchings and Hamiltonian cycles in higher-order Gabriel graphs, The \(k\)-nearest-neighbor Voronoi diagram revisited, 10-Gabriel graphs are Hamiltonian, Matchings in higher-order Gabriel graphs

Cites Work

• Toughness and Delaunay triangulations
• Generating realistic terrains with higher-order Delaunay triangulations
• Point set stratification and Delaunay depth
• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• Efficient perturbations for handling geometric degeneracies
• Higher order Delaunay triangulations
• Constrained higher order Delaunay triangulations
• Conflict-free coloring of points and simple regions in the plane
• Symbolic treatment of geometric degeneracies