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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Switzerland
Confidentiality degree is not subject to a state or trade secret
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 0302-9743
Doi http://dx.doi.org/10.1007/978-3-031-49272-3_8
Keywords in English Crossing Number; Planarity; Thickness; Fixed-parameter Tractability
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 7/4/2024 23:19.
Abstract
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.
PrintDisplayed: 15/5/2024 00:11