Planar Embeddings with Small and Uniform Faces

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Planar Embeddings with Small and Uniform Faces

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Planar Embeddings with Small and Uniform Faces

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-14179S" target="_blank" >GA14-14179S: Algoritmické, strukturální a složitostní aspekty konfigurací v rovině</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

13

Strana od-do

633-645

Název nakladatele

Springer International Publishing

Místo vydání

Heidelberg

Místo konání akce

Jeonju, Korea

Datum konání akce

15. 12. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—