Computing Cartograms with Optimal Complexity

Kód výsledku v IS VaVaI

RIV/00216208:11320/13:10190902 - isvavai.cz

Výsledek na webu

http://link.springer.com/article/10.1007%2Fs00454-013-9521-1

DOI - Digital Object Identifier

10.1007/s00454-013-9521-1

Jazyk výsledku

angličtina

Název v původním jazyce

Computing Cartograms with Optimal Complexity

Popis výsledku v původním jazyce

In a rectilinear dual of a planar graph vertices are represented by sim- ple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is opti- mal in terms of polygonal complexity as 8-sided polygons are sometimes necessary.

Název v anglickém jazyce

Computing Cartograms with Optimal Complexity

Popis výsledku anglicky

In a rectilinear dual of a planar graph vertices are represented by sim- ple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is opti- mal in terms of polygonal complexity as 8-sided polygons are sometimes necessary.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

GEGIG/11/E023: Kreslení grafů a jejich geometrické reprezentace

Návaznosti

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

Rok uplatnění

2013

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 periodika

Discrete and Computational Geometry

ISSN

0179-5376

e-ISSN

—

Svazek periodika

50

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

784-810

Kód UT WoS článku

000324494500010

EID výsledku v databázi Scopus

—