Planar Embeddings with Small and Uniform Faces
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10282715" target="_blank" >RIV/00216208:11320/14:10282715 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-13075-0_50" target="_blank" >http://dx.doi.org/10.1007/978-3-319-13075-0_50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-13075-0_50" target="_blank" >10.1007/978-3-319-13075-0_50</a>
Alternative languages
Result language
angličtina
Original language name
Planar Embeddings with Small and Uniform Faces
Original language description
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- approximationfor 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA14-14179S" target="_blank" >GA14-14179S: Algorithmic, structural and complexity aspects of configurations in the plane</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Algorithms and Computation : 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings
ISBN
978-3-319-13074-3
ISSN
0302-9743
e-ISSN
—
Number of pages
13
Pages from-to
633-645
Publisher name
Springer International Publishing
Place of publication
Heidelberg
Event location
Jeonju, Korea
Event date
Dec 15, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—