Finding Bimodal and Acyclic Orientations of Mixed Planar Graphs is NP-Complete
Vasca Navale, Maurizio Patrignani · 2011
We investigate the computational complexity of the following problem. Given a “mixed” planar graph, i.e., a planar graph where some edges are directed, orient the remaining edges in such a way that the whole graph is acyclic and admits a bimodal planar embedding, that is, a planar embedding where edges entering (exiting) each vertex appear consecutively in its circular adjacency list. We show that this extendability problem is NP-complete by first determining its complexity in the fixed embedding setting and then extending the result to the variable embedding setting.