On the Uncrossed Number of Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10490827" target="_blank" >RIV/00216208:11320/24:10490827 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/24:00139108

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.GD.2024.18" target="_blank" >https://doi.org/10.4230/LIPIcs.GD.2024.18</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.GD.2024.18" target="_blank" >10.4230/LIPIcs.GD.2024.18</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Uncrossed Number of Graphs

Popis výsledku v původním jazyce

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, acollection D of drawings of G is uncrossed if, for each edge e of G, there is a drawing in D 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 verticesand edges of G. Moreover, we prove NP-hardness of the related problem of determining the edgecrossing number of a graph G, which is the smallest number of edges of G taken over all drawings ofG that participate in a crossing. This problem was posed as open by Schaefer in his book [CrossingNumbers of Graphs 2018].

Název v anglickém jazyce

On the Uncrossed Number of Graphs

Popis výsledku anglicky

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, acollection D of drawings of G is uncrossed if, for each edge e of G, there is a drawing in D 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 verticesand edges of G. Moreover, we prove NP-hardness of the related problem of determining the edgecrossing number of a graph G, which is the smallest number of edges of G taken over all drawings ofG that participate in a crossing. This problem was posed as open by Schaefer in his book [CrossingNumbers of Graphs 2018].

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

<a href="/cs/project/GX23-04949X" target="_blank" >GX23-04949X: Stěžejní otázky diskrétní geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

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

32nd International Symposium on Graph Drawing and Network Visualization

ISBN

978-3-95977-343-0

ISSN

—

e-ISSN

—

Počet stran výsledku

13

Strana od-do

—

Název nakladatele

Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern

Místo vydání

Německo

Místo konání akce

Vienna, Austria

Datum konání akce

18. 9. 2024

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

WRD - Celosvětová akce

Kód UT WoS článku

—