Veröffentlichung

Titel:

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

AutorInnen:

Patrizio Angelini
Giordano Da Lozzo
Giuseppe Di Battista
Valentino Di Donato
Philipp Kindermann
Günter Rote
Ignaz Rutter

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), pp. 985-996

Abstract:

Given a planar graph G=(V,E) and a partition of the neighbors of each vertex v ∈ V in four sets UR(v), UL(v), DL(v), and DR(v), the problem Windrose Planarity asks to decide whether G admits a windrose-planar drawing, that is, a planar drawing in which (i) each neighbor u ∈ UR(v) is above and to the right of v, (ii) each neighbor u ∈ UL(v) is above and to the left of v, (iii) each neighbor u ∈ DL(v) is below and to the left of v, (iv) each neighbor u ∈ DR(v) is below and to the right of v, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph.

Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an O(n) ✕ O(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

Download:

Proceeding Website

BibTeX-Eintrag:

@InProceedings{ALBDKRR16, Title = {Windrose Planarity: Embedding Graphs with Direction-Constrained Edges}, Author = {Patrizio Angelini and Giordano Da Lozzo and Giuseppe Di Battista and Valentino Di Donato and Philipp Kindermann and G{\"{u}}nter Rote and Ignaz Rutter}, Booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA'16)}, Year = {2016}, Editor = {Robert Krauthgamer}, Pages = {985--996}, Publisher = {{SIAM}}, Abstract = {Given a planar graph $G=(V,E)$ and a partition of the neighbors of each vertex $v \in V$ in four sets $UR(v)$, $UL(v)$, $DL(v)$, and $DR(v)$, the problem Windrose Planarity asks to decide whether $G$ admits a \emph{windrose-planar drawing}, that is, a planar drawing in which (i) each neighbor $u \in UR(v)$ is above and to the right of $v$, (ii) each neighbor $u \in UL(v)$ is above and to the left of $v$, (iii) each neighbor $u \in DL(v)$ is below and to the left of $v$, (iv) each neighbor $u \in DR(v)$ is below and to the right of $v$, and (v) edges are represented by curves that are monotone with respect to each axis. By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a combinatorial embedding that is given as part of the input. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph admitting a windrose-planar drawing we show how to construct one with at most one bend per edge on an $O(n) \times O(n)$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.}, Doi = {10.1137/1.9781611974331.ch70} }