Faithful Representations of Graphs by Islands in the Extended Grid

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10057003" target="_blank" >RIV/00216208:11320/10:10057003 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Faithful Representations of Graphs by Islands in the Extended Grid

Popis výsledku v původním jazyce

We investigate embeddings of graphs into the infinite extended grid graph, where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k. We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k { 3 and k } 5; the cases k = 3, 4, 5 remain open.

Název v anglickém jazyce

Faithful Representations of Graphs by Islands in the Extended Grid

Popis výsledku anglicky

We investigate embeddings of graphs into the infinite extended grid graph, where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k. We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k { 3 and k } 5; the cases k = 3, 4, 5 remain open.

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

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í

2010

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

LATIN 2010: Theoretical Informatics

ISBN

978-3-642-12199-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

SPRINGER

Místo vydání

Berlin-Heidelberg

Místo konání akce

Oaxaca

Datum konání akce

19. 4. 2010

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

WRD - Celosvětová akce

Kód UT WoS článku

000279661700012