Windrose planarity: Embedding graphs with direction-constrained edges

Given a planar graph G and a partition of the neighbors of each vertex 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 us to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is N P-hard in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with n vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most 2n − 5 bends in total, which lies on the 3n × 3n grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.