Simultaneous Orthogonal Planarity
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Simultaneous Orthogonal Planarity
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-14179S" target="_blank" >GA14-14179S: Algorithmic, structural and complexity aspects of configurations in the plane</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Graph Drawing and Network Visualization
ISBN
978-3-319-50105-5
ISSN
—
e-ISSN
—
Number of pages
14
Pages from-to
532-545
Publisher name
Springer International Publishing AG
Place of publication
Cham, Switzerland
Event location
Athens
Event date
Sep 19, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—