Bend-optimal orthogonal graph drawing in the general position model

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10291626" target="_blank" >RIV/00216208:11320/14:10291626 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.comgeo.2013.03.002" target="_blank" >http://dx.doi.org/10.1016/j.comgeo.2013.03.002</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.comgeo.2013.03.002" target="_blank" >10.1016/j.comgeo.2013.03.002</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bend-optimal orthogonal graph drawing in the general position model

Popis výsledku v původním jazyce

We consider orthogonal drawings in the general position model, i.e., no two points share a coordinate. The drawings are also required to be bend minimal, i.e., each edge of a drawing in k dimensions has exactly one segment parallel to each coordinate direction that are glued together at k 1 bends. We provide a precise description of the class of graphs that admit an orthogonal drawing in the general position model in the plane. The main tools for the proof are Eulerian orientations of graphs and discrete harmonic functions. The tools developed for the planar case can also be applied in higher dimensions. We discuss two-bend drawings in three dimensions and show that K2k+2 admits a k-bend drawing in k + 1 dimensions. If we allow that a vertex is placedat infinity, we can draw K2k+3 with k bends in k + 1 dimensions.

Název v anglickém jazyce

Bend-optimal orthogonal graph drawing in the general position model

Popis výsledku anglicky

We consider orthogonal drawings in the general position model, i.e., no two points share a coordinate. The drawings are also required to be bend minimal, i.e., each edge of a drawing in k dimensions has exactly one segment parallel to each coordinate direction that are glued together at k 1 bends. We provide a precise description of the class of graphs that admit an orthogonal drawing in the general position model in the plane. The main tools for the proof are Eulerian orientations of graphs and discrete harmonic functions. The tools developed for the planar case can also be applied in higher dimensions. We discuss two-bend drawings in three dimensions and show that K2k+2 admits a k-bend drawing in k + 1 dimensions. If we allow that a vertex is placedat infinity, we can draw K2k+3 with k bends in k + 1 dimensions.

Druh

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

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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 periodika

Computational Geometry: Theory and Applications

ISSN

0925-7721

e-ISSN

—

Svazek periodika

47

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

460-468

Kód UT WoS článku

000330084600002

EID výsledku v databázi Scopus

—