2025/07/28 by Charvy, Gaspard, Masařík, Tomáš
#68R10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2507.20937
We investigate a very recent concept for visualizing various aspects of a graph in the plane using a collection of drawings introduced by Hliněný and Masařík [GD 2023]. Formally, given a graph G, we aim to find an uncrossed collection containing drawings of G in the plane such that each edge of G is not crossed in at least one drawing in the collection. The uncrossed number of G (unc(G)) is the smallest integer k such that an uncrossed collection for G of size k exists. The uncrossed number is lower-bounded by the well-known thickness, which is an edge-decomposition of G into planar graphs. This connection gives a trivial lower-bound \lceil(|E(G)|)/(3|V(G)|-6)\rceil ≤ unc(G). In a recent paper, Balko, Hliněný, Masařík, Orthaber, Vogtenhuber, and Wagner [GD 2024] presented the first non-trivial and general lower-bound on the uncrossed number. We summarize it in terms of dense graphs (where |E(G)|=ε(|V(G)|)2 for some ε>0): \lceil(|E(G)|)/(cε|V(G)|)\rceil ≤ unc(G), where cε≥ 2.82 is a constant depending on ε. We improve the lower-bound to state that \lceil(|E(G)|)/(3|V(G)|-6-√(2|E(G)|)+√(6(|V(G)|-2)))\rceil ≤ unc(G). Translated to dense graphs regime, the bound yields a multiplicative constant c'ε=3-√((2-ε)) in the expression \lceil(|E(G)|)/(c'ε|V(G)|+o(|V(G)|))\rceil ≤ unc(G). Hence, it is tight (up to low-order terms) for ε≈ (1)/(2) as warranted by complete graphs. In fact, we formulate our result in the language of the maximum uncrossed subgraph number, that is, the maximum number of edges of G that are not crossed in a drawing of G in the plane. In that case, we also provide a construction certifying that our bound is asymptotically tight (up to low-order terms) on dense graphs for all ε>0.