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

# Windrose planarity: embedding graphs with direction-constrained edges

In: *Proceedings of the 27th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA16)*, San
Francisco, January 2016, pp. 985–996.
doi:10.1137/1.9781611974331.ch70,
arXiv:1510.02659 [cs.CG].
### Abstract

Windrose planarity asks for planar drawings of a graph, where every edge is
monotone both in in the `x` and the `y`-direction. Moreover,
for each edge `uv` it is specified in which quadrant (NE, NW, SW, or
SE) `v` lies relative to `u`. While the well-known notion of
upward planarity can be used to visualize a partial order, windrose planarity
simultaneously visualize two partial orders defined by the edges of the same
graph by exploiting both the horizontal and the vertical relationship among
vertices.

Testing whether there exists a windrose-planar drawing is NP-hard in the
general case. We give a polynomial-time algorithm for the case when the
desired combinatorial embedding is specified 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. This contrasts with
the fact that straight-line windrose-planar drawings may require exponential
area.

Last update: October 12, 2015.