2014/09/15 by Giordano Da Lozzo, Vít Jelínek, Da Lozzo, Giordano +5
Computer Science · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.CG #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1409.4299
23 pages, 5 figures, extended version of 'Planar Embeddings with Small and Uniform Faces' (The 25th International Symposium on Algorithms and Computation, 2014)
arxiv created 2014/09/15 · arxiv updated 2014/09/17
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 ≤ 4 and NP-complete for k ≥ 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 ≥ 7 and even k ≥ 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.