On the Uncrossed Number of Graphs

D 2024

On the Uncrossed Number of Graphs

BALKO, Martin; Petr HLINĚNÝ; Tomáš MASAŘÍK; Joachim ORTHABER; Birgit VOGTENHUBER et al.

Základní údaje

Originální název

On the Uncrossed Number of Graphs

Autoři

BALKO, Martin; Petr HLINĚNÝ ; Tomáš MASAŘÍK; Joachim ORTHABER; Birgit VOGTENHUBER a Mirko H. WAGNER

Vydání

LIPIcs Vol. 320. Dagstuhl, Germany, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), od s. "18:1"-"18:13", 13 s. 2024

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/24:00139108

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-343-0

ISSN

Klíčová slova anglicky

Uncrossed Number; Crossing Number; Planarity; Thickness

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 20. 3. 2026 06:57, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

Visualizing a graph G in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of G to be drawn without crossings while allowing multiple different drawings of G. More formally, a collection 𝒟 of drawings of G is uncrossed if, for each edge e of G, there is a drawing in 𝒟 such that e is uncrossed. The uncrossed number unc(G) of G is then the minimum number of drawings in some uncrossed collection of G. No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík [GD 2023]. We also present a strong general lower bound on unc(G) in terms of the number of vertices and edges of G. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph G, which is the smallest number of edges of G taken over all drawings of G that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018].

Citovat

BALKO, Martin; Petr HLINĚNÝ; Tomáš MASAŘÍK; Joachim ORTHABER; Birgit VOGTENHUBER a Mirko H. WAGNER. On the Uncrossed Number of Graphs. Online. In Felsner, Stefan and Klein, Karsten. 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). LIPIcs Vol. 320. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2024, s. "18:1"-"18:13", 13 s. ISBN 978-3-95977-343-0. Dostupné z: https://doi.org/10.4230/LIPICS.GD.2024.18.

@inproceedings{2484997,
   author = {Balko, Martin and Hliněný, Petr and Masařík, Tomáš and Orthaber, Joachim and Vogtenhuber, Birgit and Wagner, Mirko H.},
   address = {Dagstuhl, Germany},
   booktitle = {32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
   doi = {https://doi.org/10.4230/LIPICS.GD.2024.18},
   edition = {LIPIcs Vol. 320},
   editor = {Felsner, Stefan and Klein, Karsten},
   keywords = {Uncrossed Number; Crossing Number; Planarity; Thickness},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-343-0},
   pages = {"18:1"-"18:13"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {On the Uncrossed Number of Graphs},
   year = {2024}
}

TY  - CONF
ID  - 2484997
AU  - Balko, Martin - Hliněný, Petr - Masařík, Tomáš - Orthaber, Joachim - Vogtenhuber, Birgit - Wagner, Mirko H.
PY  - 2024
TI  - On the Uncrossed Number of Graphs
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl, Germany
SN  - 9783959773430
KW  - Uncrossed Number
KW  - Crossing Number
KW  - Planarity
KW  - Thickness
N2  - Visualizing a graph G in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of G to be drawn without crossings while allowing multiple different drawings of G. More formally, a collection 𝒟 of drawings of G is uncrossed if, for each edge e of G, there is a drawing in 𝒟 such that e is uncrossed. The uncrossed number unc(G) of G is then the minimum number of drawings in some uncrossed collection of G. No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík [GD 2023]. We also present a strong general lower bound on unc(G) in terms of the number of vertices and edges of G. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph G, which is the smallest number of edges of G taken over all drawings of G that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018].
ER  -

BALKO, Martin; Petr HLINĚNÝ; Tomáš MASAŘÍK; Joachim ORTHABER; Birgit VOGTENHUBER a Mirko H. WAGNER. On the Uncrossed Number of Graphs. Online. In Felsner, Stefan and Klein, Karsten. \textit{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)}. LIPIcs Vol. 320. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2024, s.~''18:1''-''18:13'', 13 s. ISBN~978-3-95977-343-0. Dostupné z: https://doi.org/10.4230/LIPICS.GD.2024.18.

Přehled o publikaci