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%2F23%3A10475546" target="_blank" >RIV/00216208:11320/23:10475546 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=wx6MQE8iMO" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=wx6MQE8iMO</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S0129054123420017" target="_blank" >10.1142/S0129054123420017</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

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

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

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

1793-6373

Svazek periodika

34

Číslo periodika v rámci svazku

07

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

18

Strana od-do

807-824

Kód UT WoS článku

000984830200001

EID výsledku v databázi Scopus

2-s2.0-85175953404