### Abstract

Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that all faces have the same size, respectively.

We prove a complexity dichotomy for MINMAXFACE and show that deciding whether the maximum is at most $k$ is polynomial-time solvable for $k \leq 4$ and $\mathcal{NP}$-complete for $k \geq 5$. Further, we give a $6$-approximation for minimizing the maximum face in a planar embedding. For UNIFORMFACES, we show that the problem is $\mathcal{NP}$-complete for odd $k \geq 7$ and even $k \geq 10$. Moreover, we characterize the biconnected planar multi-graphs admitting $3$- and $4$-uniform embeddings (in a $k$-uniform embedding all faces have size $k$) and give an efficient algorithm for testing the existence of a $6$-uniform embedding.

Publication

In *25th International Symposium on Algorithms and Computation (ISAAC 2014)*

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