2010/01/06 by Jan Kratochvı́l, Kratochvil, Jan, Boris Horvat +3
Computer Science · #05C10 #05C12 #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #FOS: Mathematics #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1001.0886
openalex publication_date 2010/01/06 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
Some graphs admit drawings in the Euclidean k-space in such a (natu- ral)\nway, that edges are represented as line segments of unit length. Such drawings\nwill be called k dimensional unit distance representations. When two\nnon-adjacent vertices are drawn in the same point, we say that the\nrepresentation is degenerate. The dimension (the Euclidean dimension) of a\ngraph is defined to be the minimum integer k needed that a given graph has\nnon-degenerate k dimensional unit distance representation (with the property\nthat non-adjacent vertices are mapped to points, that are not distance one\nappart). It is proved that deciding if an input graph is homomorphic to a graph\nwith dimension k >= 2 (with the Euclidean dimension k >= 2) are NP-hard\nproblems.\n