Abstrakt
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 at most 4 and NP-complete for k at least 5.
Further, we give a 6- approximation for minimizing the maximum face in a planar embedding. For UniformFaces, we show that the problem is NP-complete for odd k at least 7 and even k at least 10.