Note on Min- k-Planar Drawings of Graphs

D 2024

Note on Min- k-Planar Drawings of Graphs

HLINĚNÝ, Petr a Lili KÖDMÖN

Základní údaje

Originální název

Note on Min- k-Planar Drawings of Graphs

Autoři

HLINĚNÝ, Petr a Lili KÖDMÖN

Vydání

LIPIcs Vol. 320. Dagstuhl, Germany, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), od s. "8:1"-"8:10", 10 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"

Kód RIV

RIV/00216224:14330/24:00139105

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-343-0

ISSN

DOI

https://doi.org/10.4230/LIPICS.GD.2024.8

EID Scopus

2-s2.0-85208783031

Klíčová slova anglicky

Crossing Number; Planarity; k-Planar Graph; Min-k-Planar Graph

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 3. 2025 13:35, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

The k-planar graphs, which are (usually with small values of k such as 1,2,3) subject to recent intense research, admit a drawing in which edges are allowed to cross, but each one edge is allowed to carry at most k crossings. In recently introduced [Binucci et al., GD 2023] min-k-planar drawings of graphs, edges may possibly carry more than k crossings, but in any two crossing edges, at least one of the two must have at most k crossings. In both concepts, one may consider general drawings or a popular restricted concept of drawings called simple. In a simple drawing, every two edges are allowed to cross at most once, and any two edges which share a vertex are forbidden to cross. While, regarding the former concept, it is for k ≤ 3 known (but perhaps not widely known) that every general k-planar graph admits a simple k-planar drawing and this ceases to be true for any k ≤ 4, the difference between general and simple drawings in the latter concept is more striking. We prove that there exist graphs with a min-2-planar drawing, or with a min-3-planar drawing avoiding crossings of adjacent edges, which have no simple min-k-planar drawings for arbitrarily large fixed k.

Citovat

HLINĚNÝ, Petr a Lili KÖDMÖN. Note on Min- k-Planar Drawings 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. "8:1"-"8:10", 10 s. ISBN 978-3-95977-343-0. Dostupné z: https://doi.org/10.4230/LIPICS.GD.2024.8.

@inproceedings{2484960,
   author = {Hliněný, Petr and Ködmön, Lili},
   address = {Dagstuhl, Germany},
   booktitle = {32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
   doi = {https://doi.org/10.4230/LIPICS.GD.2024.8},
   edition = {LIPIcs Vol. 320},
   editor = {Felsner, Stefan and Klein, Karsten},
   keywords = {Crossing Number; Planarity; k-Planar Graph; Min-k-Planar Graph},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-343-0},
   pages = {"8:1"-"8:10"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {Note on Min- k-Planar Drawings of Graphs},
   year = {2024}
}

TY  - CONF
ID  - 2484960
AU  - Hliněný, Petr - Ködmön, Lili
PY  - 2024
TI  - Note on Min- k-Planar Drawings of Graphs
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl, Germany
SN  - 9783959773430
KW  - Crossing Number
KW  - Planarity
KW  - k-Planar Graph
KW  - Min-k-Planar Graph
N2  - The k-planar graphs, which are (usually with small values of k such as 1,2,3) subject to recent intense research, admit a drawing in which edges are allowed to cross, but each one edge is allowed to carry at most k crossings. In recently introduced [Binucci et al., GD 2023] min-k-planar drawings of graphs, edges may possibly carry more than k crossings, but in any two crossing edges, at least one of the two must have at most k crossings. In both concepts, one may consider general drawings or a popular restricted concept of drawings called simple. In a simple drawing, every two edges are allowed to cross at most once, and any two edges which share a vertex are forbidden to cross. While, regarding the former concept, it is for k ≤ 3 known (but perhaps not widely known) that every general k-planar graph admits a simple k-planar drawing and this ceases to be true for any k ≤ 4, the difference between general and simple drawings in the latter concept is more striking. We prove that there exist graphs with a min-2-planar drawing, or with a min-3-planar drawing avoiding crossings of adjacent edges, which have no simple min-k-planar drawings for arbitrarily large fixed k.
ER  -

HLINĚNÝ, Petr a Lili KÖDMÖN. Note on Min- k-Planar Drawings 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.~''8:1''-''8:10'', 10 s. ISBN~978-3-95977-343-0. Dostupné z: https://doi.org/10.4230/LIPICS.GD.2024.8.

Přehled o publikaci