Minimizing an Uncrossed Collection of Drawings

D 2023

Minimizing an Uncrossed Collection of Drawings

HLINĚNÝ, Petr and Tomáš MASAŘÍK

Basic information

Original name

Minimizing an Uncrossed Collection of Drawings

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution) and Tomáš MASAŘÍK (203 Czech Republic)

Edition

14465. vyd. Switzerland, Graph Drawing 2023, p. 110-123, 14 pp. 2023

Publisher

Springer, Cham

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/23:00131579

Organization unit

Faculty of Informatics

ISBN

978-3-031-49271-6

ISSN

DOI

http://dx.doi.org/10.1007/978-3-031-49272-3_8

UT WoS

001207939600008

Keywords in English

Crossing Number; Planarity; Thickness; Fixed-parameter Tractability

Abstract

V originále

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.

Citovat

HLINĚNÝ, Petr and Tomáš MASAŘÍK. Minimizing an Uncrossed Collection of Drawings. Online. In Bekos, M.A., Chimani, M. Graph Drawing 2023. 14465th ed. Switzerland: Springer, Cham, 2023, p. 110-123. ISBN 978-3-031-49271-6. Available from: https://dx.doi.org/10.1007/978-3-031-49272-3_8.

@inproceedings{2306238,
   author = {Hliněný, Petr and Masařík, Tomáš},
   address = {Switzerland},
   booktitle = {Graph Drawing 2023},
   doi = {http://dx.doi.org/10.1007/978-3-031-49272-3_8},
   edition = {14465},
   editor = {Bekos, M.A., Chimani, M.},
   keywords = {Crossing Number; Planarity; Thickness; Fixed-parameter Tractability},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Switzerland},
   isbn = {978-3-031-49271-6},
   pages = {110-123},
   publisher = {Springer, Cham},
   title = {Minimizing an Uncrossed Collection of Drawings},
   year = {2023}
}

TY  - JOUR
ID  - 2306238
AU  - Hliněný, Petr - Masařík, Tomáš
PY  - 2023
TI  - Minimizing an Uncrossed Collection of Drawings
PB  - Springer, Cham
CY  - Switzerland
SN  - 9783031492716
KW  - Crossing Number
KW  - Planarity
KW  - Thickness
KW  - Fixed-parameter Tractability
N2  - 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.
ER  -

HLINĚNÝ, Petr and Tomáš MASAŘÍK. Minimizing an Uncrossed Collection of Drawings. Online. In Bekos, M.A., Chimani, M. \textit{Graph Drawing 2023}. 14465th ed. Switzerland: Springer, Cham, 2023, p.~110-123. ISBN~978-3-031-49271-6. Available from: https://dx.doi.org/10.1007/978-3-031-49272-3\_{}8.

Detailed Information on Publication Record