Given a planar graph G(V, E) and a partition of the neighbors of each vertex v σ V in four sets v, v, v, and 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 σ v is above and to the right of v, (ii) each neighbor u σ v is above and to the left of v, (iii) each neighbor u σ v is below and to the left of v, (iv) each neighbor u σ 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 0(n) x 0(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

Angelini, P., DA LOZZO, G., DI BATTISTA, G., DI DONATO, V., Kindermann, P., Rote, G., et al. (2016). Windrose planarity: Embedding graphs with direction-constrained edges. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.985-996). Association for Computing Machinery.

Windrose planarity: Embedding graphs with direction-constrained edges

ANGELINI, PATRIZIO;DA LOZZO, GIORDANO;DI BATTISTA, Giuseppe;DI DONATO, VALENTINO;
2016

Abstract

Given a planar graph G(V, E) and a partition of the neighbors of each vertex v σ V in four sets v, v, v, and 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 σ v is above and to the right of v, (ii) each neighbor u σ v is above and to the left of v, (iii) each neighbor u σ v is below and to the left of v, (iv) each neighbor u σ 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 0(n) x 0(n) grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.
9781510819672
9781510819672
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/299178
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact