On the Computational Complexity of Degenerate Unit Distance Representations of Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Computational Complexity of Degenerate Unit Distance Representations of Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Computational Complexity of Degenerate Unit Distance Representations of Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

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

Název statě ve sborníku

COMBINATORIAL ALGORITHMS

ISBN

978-3-642-19221-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

274-285

Název nakladatele

SPRINGER

Místo vydání

Berlin

Místo konání akce

Londýn

Datum konání akce

26. 7. 2010

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000290418700028