Minimizing an Uncrossed Collection of Drawings

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F23%3A00131579" target="_blank" >RIV/00216224:14330/23:00131579 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-031-49272-3_8" target="_blank" >http://dx.doi.org/10.1007/978-3-031-49272-3_8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-49272-3_8" target="_blank" >10.1007/978-3-031-49272-3_8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Minimizing an Uncrossed Collection of Drawings

Popis výsledku v původním jazyce

In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is useful for graph visualization. We propose investigating a property where each edge is not crossed in at least one drawing in the collection. We call such collection uncrossed. This property is motivated by a quintessential problem of the crossing number, where one asks for a drawing where the number of edge crossings is minimum. Indeed, if we are allowed to visualize only one drawing, then the one which minimizes the number of crossings is probably the neatest for the first orientation. However, a collection of drawings where each highlights a different aspect of a graph without any crossings could shed even more light on the graph’s structure. We propose two definitions. First, the uncrossed number, minimizes the number of graph drawings in a collection, satisfying the uncrossed property. Second, the uncrossed crossing number, minimizes the total number of crossings in the collection that satisfy the uncrossed property. For both definitions, we establish initial results. We prove that the uncrossed crossing number is NP-hard, but there is an algorithm parameterized by the solution size.

Název v anglickém jazyce

Minimizing an Uncrossed Collection of Drawings

Popis výsledku anglicky

In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is useful for graph visualization. We propose investigating a property where each edge is not crossed in at least one drawing in the collection. We call such collection uncrossed. This property is motivated by a quintessential problem of the crossing number, where one asks for a drawing where the number of edge crossings is minimum. Indeed, if we are allowed to visualize only one drawing, then the one which minimizes the number of crossings is probably the neatest for the first orientation. However, a collection of drawings where each highlights a different aspect of a graph without any crossings could shed even more light on the graph’s structure. We propose two definitions. First, the uncrossed number, minimizes the number of graph drawings in a collection, satisfying the uncrossed property. Second, the uncrossed crossing number, minimizes the total number of crossings in the collection that satisfy the uncrossed property. For both definitions, we establish initial results. We prove that the uncrossed crossing number is NP-hard, but there is an algorithm parameterized by the solution size.

Druh

D - Stať ve sborníku

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 statě ve sborníku

Graph Drawing 2023

ISBN

9783031492716

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

110-123

Název nakladatele

Springer, Cham

Místo vydání

Switzerland

Místo konání akce

Italy

Datum konání akce

1. 1. 2023

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

WRD - Celosvětová akce

Kód UT WoS článku

—