A Unified FPT Framework for Crossing Number Problems

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00144018" target="_blank" >RIV/00216224:14330/25:00144018 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

A Unified FPT Framework for Crossing Number Problems

Original language description

The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to Z_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2025

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

33rd Annual European Symposium on Algorithms (ESA 2025)

ISBN

—

ISSN

1868-8969

e-ISSN

—

Number of pages

18

Pages from-to

„21:1“-„21:18“

Publisher name

Schloss Dagstuhl - Leibniz Center for Informatics

Place of publication

Dagstuhl, Německo

Event location

Warsaw, Poland

Event date

Sep 15, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—