On the Uncrossed Number of Graphs

Result code in 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>

Alternative codes found

RIV/00216224:14330/24:00139108

Result on the web

<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>

Result language

angličtina

Original language name

On the Uncrossed Number of Graphs

Original language description

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].

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>

Continuities

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

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

32nd International Symposium on Graph Drawing and Network Visualization

ISBN

978-3-95977-343-0

ISSN

—

e-ISSN

—

Number of pages

13

Pages from-to

—

Publisher name

Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern

Place of publication

Německo

Event location

Vienna, Austria

Event date

Sep 18, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—