On locally Gabriel geometric graphs

DOI10.1007/s00373-014-1482-5zbMath1321.05062arXiv1207.4082OpenAlexW2013066311MaRDI QIDQ497339

Abhijeet Khopkar, Sathish Govindarajan

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4082

zbMATH Keywords

independent setconvex point setsedge complexityGabriel graphsgeometric proximity graphslocally Gabriel graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Extremal problems in discrete geometry
• A lower bound on the number of unit distances between the vertices of a convex polygon
• The unit distance problem for centrally symmetric convex polygons
• Research Problems in Discrete Geometry
• A fast algorithm for computing longest common subsequences
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Independence numbers of locally sparse graphs and a Ramsey type problem
• PROXIMITY STRUCTURES FOR GEOMETRIC GRAPHS
• On locally Delaunay geometric graphs
• On Sets of Distances of n Points
• The maximum number of times the same distance can occur among the vertices of a convex \(n\)-gon is \(O(n\log n)\)