Simultaneous Orthogonal Planarity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331739" target="_blank" >RIV/00216208:11320/16:10331739 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-319-50106-2_41" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-319-50106-2_41</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-50106-2_41" target="_blank" >10.1007/978-3-319-50106-2_41</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Simultaneous Orthogonal Planarity

Popis výsledku v původním jazyce

We introduce and study the ORTHOSEFE-k problem: Given k planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the k graphs? We show that the problem is NP-complete for kGREATER-THAN OR EQUAL TO3 even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for kGREATER-THAN OR EQUAL TO2 even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for k=2 when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.

Název v anglickém jazyce

Simultaneous Orthogonal Planarity

Popis výsledku anglicky

We introduce and study the ORTHOSEFE-k problem: Given k planar graphs each with maximum degree 4 and the same vertex set, do they admit an OrthoSEFE, that is, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in distinct graphs are assigned the same path and such that the assignment induces a planar orthogonal drawing of each of the k graphs? We show that the problem is NP-complete for kGREATER-THAN OR EQUAL TO3 even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for kGREATER-THAN OR EQUAL TO2 even if the shared graph consists of a cycle and of isolated vertices. Whereas the problem is polynomial-time solvable for k=2 when the union graph has maximum degree five and the shared graph is biconnected. Further, when the shared graph is biconnected and has sunflower intersection, we show that every positive instance has an OrthoSEFE with at most three bends per edge.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-14179S" target="_blank" >GA14-14179S: Algoritmické, strukturální a složitostní aspekty konfigurací v rovině</a><br>

Návaznosti

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

Rok uplatnění

2016

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 Drawing and Network Visualization

ISBN

978-3-319-50105-5

ISSN

—

e-ISSN

—

Počet stran výsledku

14

Strana od-do

532-545

Název nakladatele

Springer International Publishing AG

Místo vydání

Cham, Switzerland

Místo konání akce

Athens

Datum konání akce

19. 9. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

—