This HTML5 document contains 48 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n18http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n14http://purl.org/net/nknouf/ns/bibtex#
n6http://localhost/temp/predkladatel/
n25http://linked.opendata.cz/resource/domain/vavai/projekt/
n11http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n10http://linked.opendata.cz/resource/domain/vavai/subjekt/
n9http://linked.opendata.cz/ontology/domain/vavai/
n23https://schema.org/
n19http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
rdfshttp://www.w3.org/2000/01/rdf-schema#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n13http://bibframe.org/vocab/
n16http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F11%3A10100204%21RIV12-MSM-11320___/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n22http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n8http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n24http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n4http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F11%3A10100204%21RIV12-MSM-11320___
rdf:type
n9:Vysledek skos:Concept
rdfs:seeAlso
http://dx.doi.org/10.1007/978-3-642-19222-7_28
dcterms: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. 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.
dcterms:title
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
skos:prefLabel
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
skos:notation
RIV/00216208:11320/11:10100204!RIV12-MSM-11320___
n9:predkladatel
n10:orjk%3A11320
n3:aktivita
n8:Z n8:P
n3:aktivity
P(1M0545), Z(MSM0021620838)
n3:dodaniDat
n4:2012
n3:domaciTvurceVysledku
n11:1123580
n3:druhVysledku
n20:D
n3:duvernostUdaju
n7:S
n3:entitaPredkladatele
n16:predkladatel
n3:idSjednocenehoVysledku
218184
n3:idVysledku
RIV/00216208:11320/11:10100204
n3:jazykVysledku
n22:eng
n3:klicovaSlova
Graph; Representation; Computational Complexity
n3:klicoveSlovo
n17:Computational%20Complexity n17:Representation n17:Graph
n3:kontrolniKodProRIV
[0855D4AE8190]
n3:mistoKonaniAkce
Londýn
n3:mistoVydani
Berlin
n3:nazevZdroje
COMBINATORIAL ALGORITHMS
n3:obor
n24:IN
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
3
n3:projekt
n25:1M0545
n3:rokUplatneniVysledku
n4:2011
n3:tvurceVysledku
Kratochvíl, Jan Horvat, Boris Pisanski, Tomaz
n3:typAkce
n18:WRD
n3:wos
000290418700028
n3:zahajeniAkce
2010-07-26+02:00
n3:zamer
n19:MSM0021620838
s:issn
0302-9743
s:numberOfPages
12
n13:doi
10.1007/978-3-642-19222-7_28
n14:hasPublisher
SPRINGER
n23:isbn
978-3-642-19221-0
n6:organizacniJednotka
11320