PROXIMITY GRAPHS: E, δ, Δ, χ AND ω

DOI10.1142/S0218195912500112zbMath1267.05072MaRDI QIDQ5300005

Ferran Hurtado, Maria Saumell, David R. Wood, Vida Dujmović, Vera Sacristán, Stefan Langerman, Prosenjit Bose, John Iacono, Henk G. Meijer

Publication date: 24 June 2013

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

Full work available at URL: https://doi.org/10.1142/s0218195912500112

zbMATH Keywords

geometric graphs; proximity graphs; graph-theoretic properties

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

Related Items

Graph product structure for non-minor-closed classes, Computational complexity of the vertex cover problem in the class of planar triangulations, 10-Gabriel graphs are Hamiltonian

Cites Work

• On crossing numbers of geometric proximity graphs
• Toughness and Delaunay triangulations
• On the average length of Delaunay triangulations
• The expected size of some graphs in computational geometry
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Some extremal results on circles containing points
• The relative neighbourhood graph of a finite planar set
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Transitions in geometric minimum spanning trees
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Circles through two points that always enclose many points
• On nearest-neighbor graphs
• On circles containing the maximum number of points
• On the homogeneous planar Poisson point process
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
• On the expected maximum degree of Gabriel and Yao graphs
• Some properties of the planar Euclidean relative neighbourhood graph
• 20‐relative neighborhood graphs are hamiltonian