Nearest Neighbour Graph Realizability is NP-hard.

Peter Eades, Sue Whitesides

Browse the full LATIN paper archive.