Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10283069" target="_blank" >RIV/00216208:11320/14:10283069 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-12340-0_12" target="_blank" >http://dx.doi.org/10.1007/978-3-319-12340-0_12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-12340-0_12" target="_blank" >10.1007/978-3-319-12340-0_12</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

Popis výsledku v původním jazyce

Planar graphs are known to have geometric representations of various types, e.g. as contacts of disks, triangles or - in the bipartite case - vertical and horizontal segments. It is known that such representations can be drawn in linear time, we here wonder whether it is as easy to decide whether a partial representation can be completed to a representation of the whole graph. We show that in each of the cases above, this problem becomes NP-hard. These are the first classes of geometric graphs where extending partial representations is provably harder than recognition, as opposed to e.g. interval graphs, circle graphs, permutation graphs or even standard representations of plane graphs. On the positive side we give two polynomial time algorithms for the grid contact case. The first one is for the case when all vertical segments are pre-represented (note: the problem remains NP-complete when a subset of the vertical segments is specified, even if none of the horizontals are). Secondly,

Název v anglickém jazyce

Contact Representations of Planar Graphs: Extending a Partial Representation is Hard

Popis výsledku anglicky

Planar graphs are known to have geometric representations of various types, e.g. as contacts of disks, triangles or - in the bipartite case - vertical and horizontal segments. It is known that such representations can be drawn in linear time, we here wonder whether it is as easy to decide whether a partial representation can be completed to a representation of the whole graph. We show that in each of the cases above, this problem becomes NP-hard. These are the first classes of geometric graphs where extending partial representations is provably harder than recognition, as opposed to e.g. interval graphs, circle graphs, permutation graphs or even standard representations of plane graphs. On the positive side we give two polynomial time algorithms for the grid contact case. The first one is for the case when all vertical segments are pre-represented (note: the problem remains NP-complete when a subset of the vertical segments is specified, even if none of the horizontals are). Secondly,

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

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

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-319-12339-4

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

139-151

Název nakladatele

Springer Berlin Heidelberg

Místo vydání

Neuvedeno

Místo konání akce

Nouan-le-Fuzelier

Datum konání akce

25. 6. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

—