Planar Embeddings with Small and Uniform Faces

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 \le 4\) and NP-complete for \(k \ge 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 \ge 7\) and even \(k \ge 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.