Veröffentlichung

Titel:

Simultaneous Orthogonal Planarity

AutorInnen:

Patrizio Angelini
Steven Chaplick
Sabine Cornelsen
Giordano Da Lozzo
Giuseppe Di Battista
Peter Eades
Philipp Kindermann
Jan Kratochvíl
Fabian Lipp
Ignaz Rutter

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD'16), pp. 532-545

Abstract:

We introduce and study the OrthoSEFE-k problem: Given k planar graphs each with maximum degree 4 and the same vertex set, 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 kgraphs? We show that the problem is NP-complete for k ≥ 3 even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for k ≥ 2 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-k with at most three bends per edge.

Download:

Springer

BibTeX-Eintrag:

@InProceedings{accddekklr-sop-gd16, Title = {Simultaneous Orthogonal Planarity}, Author = {Patrizio Angelini and Steven Chaplick and Sabine Cornelse and Giordano Da Lozzo and Giuseppe Di Battista and Peter Eades and Philipp Kindermann and Jan Kratochv{\'{\i}}l and Fabian Lipp and Ignaz Rutter}, Booktitle = {Proc. 24th International Symposium on Graph Drawing and Network Visualization (GD'16)}, Year = {2016}, Editor = {Yifan Hu and Martin N{\"o}llenburg}, Pages = {532--545}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, Volume = {9801}, Abstract = {We introduce and study the OrthoSEFE-$k$ problem: Given $k$ planar graphs each with maximum degree 4 and the same vertex set, 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 $k \geq 3$ even if the shared graph is a Hamiltonian cycle and has sunflower intersection and for $k \geq 2$ 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-$k$ with at most three bends per edge.}, Doi = {10.1007/978-3-319-50106-2_41} }