Nearest neighbour graph realizability is NP-hard

DOI10.1007/3-540-59175-3_93zbMath1495.68166OpenAlexW1847702720MaRDI QIDQ5096336

Peter Eades, S. H. Whitesides

Publication date: 16 August 2022

Published in: LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59175-3_93

zbMATH Keywords

pattern recognitiongeometric graphscomputational geometrygraph drawingNP-hardnesscomplexity theoryproximity graphsnearest neighbour 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 representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

The rectangle of influence drawability problem

Cites Work

• Realizability of Delaunay triangulations
• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• Algorithms for drawing graphs: An annotated bibliography
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Unnamed Item

This page was built for publication: Nearest neighbour graph realizability is NP-hard