On the computational complexity of degenerate unit distance representations of graphs

Jan Kratochvil, Boris Horvat, Tomaz Pisanski

Some graphs admit drawings in the Euclidean k-space in such a (natu- ral) way, that edges are represented as line segments of unit length. Such drawings will be called k dimensiona…