### Abstract

Consider the following combinatorial problem$:$ Given a planar graph $G$ and a set of simple cycles $\mathcal C$ in $G$, find a planar embedding $\mathcal E$ of $G$ such that the number of cycles in $\mathcal C$ that bound a face in $\mathcal E$ is maximized. This problem, called Max Facial $\mathcal C$-Cycles, was first studied by Mutzel and Weiskircher [IPCO ‘99] and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002].

We establish a tight border of tractability for Max Facial $\mathcal C$-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial $\mathcal C$-Cycles. Namely, we give a $2$-approximation for series-parallel graphs and a $(4+\varepsilon)$-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems.

Publication

In *29th International Symposium on Algorithms and Computation (ISAAC 2018)*

###### Assistant Professor (RTDb)

My research interests are in Algorithm Engineering and Complexity, focused in particular on the theoretical and algorithmic challenges arising from the visualization of graphs.