On the Computational Complexity of Degenerate Unit Distance Representations of Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100204" target="_blank" >RIV/00216208:11320/11:10100204 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-19222-7_28" target="_blank" >http://dx.doi.org/10.1007/978-3-642-19222-7_28</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-19222-7_28" target="_blank" >10.1007/978-3-642-19222-7_28</a>

Result language
angličtina
Original language name
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
Original language description
Some graphs admit drawings in the Euclidean k-space in such a (natural) way, that edges are represented as line segments of unit length. Such embeddings are called k-dimensional unit distance representations. The embedding is strict if the distances of points representing nonadjacent pairs of vertices are different than 1. When two non-adjacent vertices are drawn in the same point, we say that the representation is degenerate. Computational complexity of nondegenerate embaldings has been studied before.We initiate the study of the computational complexity of (possibly) degenerate embeddings. In particular we prove that for every k }= 2, deciding if an input graph has a (possibly) degenerate k-dimensional unit distance representation is NP-hard.
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)