On computational complexity of length embeddability of graphs

Abstract

A graph $G$ is embeddable in ${\mathbb{R}}^d$ if vertices of $G$ can be assigned with points of ${\mathbb{R}}^d$ in such a way that all pairs of adjacent vertices are at the distance 1. We show that verifying embeddability of a given graph in ${\mathbb{R}}^d$ is NP-hard in the case $d>2$ for all reasonable notions of embeddability.

12 pages, 1 figure