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

1. 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.  →BibTeX
2. ACM Transactions on Algorithms 14 (September 2018), Article 54, pp. 54:1–54:24. doi:10.1145/3239561 arXiv:1510.02659 [cs.CG].  →BibTeX

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.