Maximizing the maximum degree in ordered nearest neighbor graphs

DOI10.1016/J.COMGEO.2025.102229MaRDI QIDQ6873625zbMATH OpenFDO

Authors Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh, Ji Zeng

Publication date 16 January 2026

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COMGEO.2025.102229

zbMATH Keywords

Euclidean spacemaximum degreenearest neighbor graphordered graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35)

Cites work

• A survey on the kissing numbers.
• Abstract sphere-of-influence graphs
• Approximating geometric bottleneck shortest paths
• Computational geometry. Algorithms and applications.
• Constructing plane spanners of bounded degree and low weight
• Covering convex bodies by translates of convex bodies
• Geometric Spanner Networks
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1424297 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• Independent sets in hypergraphs with a forbidden link
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On nearest-neighbor graphs
• On prescribing total orders and preorders to pairwise distances of points in Euclidean space
• Ordered theta graphs
• Sparse geometric graphs with small dilation

Cited in

(1)

• Ordered Yao graphs: maximum degree, edge density, and clique numbers

This page was built for publication: Maximizing the maximum degree in ordered nearest neighbor graphs

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