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. -
DA LOZZO, G., Vìt, J., Jan, K., Ignaz, R. (2014). Planar Embeddings with Small and Uniform Faces. In The 25th International Symposium on Algorithms and Computation (ISAAC 2014) (pp.633-645). Springer-Verlag [10.1007/978-3-319-13075-0_50].
Planar Embeddings with Small and Uniform Faces
DA LOZZO, GIORDANO;
2014-01-01
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 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. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
