In this paper, we study the computational complexity of constructing 4-modal embeddings of directed planar graphs, which are motivated by the recently introduced planar L-drawings [Chaplick et al., GD '17]. We give a linear-time algorithm for testing the existence of 4-modal embeddings for the class of partial 2-trees and show a complexity dichotomy for this problem in general planar graphs with respect to the maximum degree $\Delta$. More specifically, we prove NP-completeness for biconnected planar graphs with $\Delta\ge 7$ and we extend the algorithm for partial 2-trees to a linear-time algorithm for simply-connected planar graphs with $\Delta\le 6$. The latter algorithmic result is based on decomposing the input graph into its triconnected components via SPQR-trees and on handling the complexity of the rigid components by means of a small set of reduction rules. Interestingly, we show that the algorithmic core of the problem can be tackled by means of Turing reductions to special instances of NAESAT that can be solved in linear time.
(Based on joint work with Giordano Da Lozzo and Michael T. Goodrich.)