## February 2, 2018:

# 4-Modal Embeddings of Directed Graphs

## Juan Besa

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.)