HARDNESS RESULTS FOR COMPUTING OPTIMAL LOCALLY GABRIEL GRAPHS

DOI10.1142/S0218195914500071zbMath1314.68349arXiv1110.1180OpenAlexW2157114458MaRDI QIDQ2939919

Sathish Govindarajan, Abhijeet Khopkar

Publication date: 23 January 2015

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

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

zbMATH Keywords

dilationGabriel graphsgeometric proximity graphslocally Gabriel graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Proximity graphs inside large weighted graphs

Cites Work

• Local solutions for global problems in wireless networks
• On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
• COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD
• PROXIMITY STRUCTURES FOR GEOMETRIC GRAPHS
• On Sets of Distances of n Points

This page was built for publication: HARDNESS RESULTS FOR COMPUTING OPTIMAL LOCALLY GABRIEL GRAPHS