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

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

Namespace Prefixes

PrefixIRI
n21http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
n7http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F11%3A10125858%21RIV13-MSM-11320___/
dctermshttp://purl.org/dc/terms/
n14http://purl.org/net/nknouf/ns/bibtex#
n9http://localhost/temp/predkladatel/
n6http://linked.opendata.cz/resource/domain/vavai/projekt/
n4http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n22http://linked.opendata.cz/resource/domain/vavai/subjekt/
n15http://linked.opendata.cz/ontology/domain/vavai/
n16https://schema.org/
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/
n19http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n24http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n23http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n11http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F11%3A10125858%21RIV13-MSM-11320___
rdf:type
skos:Concept n15:Vysledek
rdfs:seeAlso
http://link.springer.com/chapter/10.1007%2F978-3-642-25870-1_9?LI=true
dcterms:description
The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G to H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar. PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvil asked whether there are non-trivial graphs for which Cover(H) is NP-complete but PlanarCover(H) belongs to P. We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of PlanarCover(H) in these cases. The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G to H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar. PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvil asked whether there are non-trivial graphs for which Cover(H) is NP-complete but PlanarCover(H) belongs to P. We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of PlanarCover(H) in these cases.
dcterms:title
On the Complexity of Planar Covering of Small Graphs On the Complexity of Planar Covering of Small Graphs
skos:prefLabel
On the Complexity of Planar Covering of Small Graphs On the Complexity of Planar Covering of Small Graphs
skos:notation
RIV/00216208:11320/11:10125858!RIV13-MSM-11320___
n15:predkladatel
n22:orjk%3A11320
n3:aktivita
n20:S n20:P
n3:aktivity
P(1M0545), P(ME09074), S
n3:dodaniDat
n11:2013
n3:domaciTvurceVysledku
n4:3108414 n4:4558286 n4:6078591 n4:5278880 n4:5775485
n3:druhVysledku
n23:D
n3:duvernostUdaju
n13:S
n3:entitaPredkladatele
n7:predkladatel
n3:idSjednocenehoVysledku
218181
n3:idVysledku
RIV/00216208:11320/11:10125858
n3:jazykVysledku
n24:eng
n3:klicovaSlova
planar graph; planar cover; NP-complete
n3:klicoveSlovo
n5:planar%20graph n5:NP-complete n5:planar%20cover
n3:kontrolniKodProRIV
[DE6CBC8B2806]
n3:mistoKonaniAkce
Teplá
n3:mistoVydani
Berlin Heidelberg
n3:nazevZdroje
Lecture Notes in Computer Science
n3:obor
n12:IN
n3:pocetDomacichTvurcuVysledku
5
n3:pocetTvurcuVysledku
5
n3:projekt
n6:ME09074 n6:1M0545
n3:rokUplatneniVysledku
n11:2011
n3:tvurceVysledku
Bílka, Ondřej Klavík, Pavel Tancer, Martin Jirásek, Jozef Volec, Jan
n3:typAkce
n21:WRD
n3:zahajeniAkce
2011-06-21+02:00
s:issn
0302-9743
s:numberOfPages
12
n19:doi
10.1007/978-3-642-25870-1_9
n14:hasPublisher
Springer-Verlag
n16:isbn
978-3-642-25869-5
n9:organizacniJednotka
11320