Planar Embeddings with Small and Uniform Faces
Venerdì 5 dicembre 2014 Ore 16:00-17:00
Sala Riunioni, 1° piano, Dipartimento di Ingegneria, Università Roma Tre
Via della Vasca Navale, 79, Roma
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 ≤ 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 em- beddings (in a k-uniform embedding all faces have size k) and give an efficient algorithm for testing the existence of a 6-uniform embedding.
This work will be presented at the 25th International Symposium on Algorithms and Computation 15-17 December 2014, Jeonju, Korea.
Joint work with Vít Jelínek, Jan Kratochvíl, and Ignaz Rutter.
