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.