Drawing Simultaneously Embedded Graphs with Few Bends

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-45803-7_4" target="_blank" >http://dx.doi.org/10.1007/978-3-662-45803-7_4</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-45803-7_4" target="_blank" >10.1007/978-3-662-45803-7_4</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Drawing Simultaneously Embedded Graphs with Few Bends

Popis výsledku v původním jazyce

We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs.

Název v anglickém jazyce

Drawing Simultaneously Embedded Graphs with Few Bends

Popis výsledku anglicky

We study the problem of drawing simultaneously embedded graphs with few bends. We show that for any simultaneous embedding with fixed edges (Sefe) of two graphs, there exists a corresponding drawing realizing this embedding such that common edges are drawn as straight-line segments and each exclusive edge has a constant number of bends. If the common graph is biconnected and induced, a straight-line drawing exists. This yields the first efficient testing algorithm for simultaneous geometric embedding (Sge) for a non-trivial class of graphs.

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

Graph Drawing

ISBN

978-3-662-45802-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

40-51

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Wurzburg

Datum konání akce

24. 9. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

—