1. On the computational complexity of degenerate unit distance representations of graphs
- Author
-
Kratochvil, Jan, Horvat, Boris, and Pisanski, Tomaz
- Subjects
Mathematics - Combinatorics ,05C62, 05C12, 05C10 - Abstract
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 dimensional unit distance representations. When two non-adjacent vertices are drawn in the same point, we say that the representation is degenerate. The dimension (the Euclidean dimension) of a graph is defined to be the minimum integer k needed that a given graph has non-degenerate k dimensional unit distance representation (with the property that non-adjacent vertices are mapped to points, that are not distance one appart). It is proved that deciding if an input graph is homomorphic to a graph with dimension k >= 2 (with the Euclidean dimension k >= 2) are NP-hard problems., Comment: 11 pages, 6 figures
- Published
- 2010