Parameterized Complexity of Graph Planarity with Restricted Cyclic Orders

We study the complexity of testing whether a biconnected graph G = (V, E) is planar with the additional constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are conveniently described by associating every vertex v of G with a set D(v) of FPQ-trees. Let tw be the treewidth of G and let D-max = max(v is an element of V) vertical bar D(v)vertical bar, i.e., the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw + D-max ; for a contrast, we prove that the problem is paraNP-hard when parameterized by D-max only and it is W[1]-hard when parameterized by tw only. We also apply our techniques to the problem of testing whether a clustered graph is NodeTrix planar with fixed sides. We extend a result by Di Giacomo et al. [Algorithmica, 2019] and prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of the clusters plus the treewidth of the graph obtained by collapsing these clusters to single vertices, provided that this graph is biconnected.