A Unified FPT Framework for Crossing Number Problems

D 2025

A Unified FPT Framework for Crossing Number Problems

COLIN DE VERDIÈRE, Éric a Petr HLINĚNÝ

Základní údaje

Originální název

A Unified FPT Framework for Crossing Number Problems

Autoři

COLIN DE VERDIÈRE, Éric a Petr HLINĚNÝ

Vydání

LIPIcs 351. Dagstuhl, Německo, 33rd Annual European Symposium on Algorithms (ESA 2025), od s. "21:1"-"21:18", 18 s. 2025

Nakladatel

Schloss Dagstuhl - Leibniz Center for Informatics

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/25:00144018

Organizační jednotka

Fakulta informatiky

ISSN

DOI

https://doi.org/10.4230/LIPIcs.ESA.2025.21

EID Scopus

2-s2.0-105019038135

Klíčová slova anglicky

computational geometry; fixed-parameter tractability; graph drawing; graph embedding; crossing number; two-dimensional simplicial complex

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 4. 2026 11:18, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 ℤ_+ ∪ {∞}, 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.

Citovat

COLIN DE VERDIÈRE, Éric a Petr HLINĚNÝ. A Unified FPT Framework for Crossing Number Problems. Online. In 33rd Annual European Symposium on Algorithms (ESA 2025). LIPIcs 351. Dagstuhl, Německo: Schloss Dagstuhl - Leibniz Center for Informatics, 2025, s. "21:1"-"21:18", 18 s. ISSN 1868-8969. Dostupné z: https://doi.org/10.4230/LIPIcs.ESA.2025.21.

@inproceedings{2561783,
   author = {Colin de Verdière, Éric and Hliněný, Petr},
   address = {Dagstuhl, Německo},
   booktitle = {33rd Annual European Symposium on Algorithms (ESA 2025)},
   doi = {https://doi.org/10.4230/LIPIcs.ESA.2025.21},
   edition = {LIPIcs 351},
   keywords = {computational geometry; fixed-parameter tractability; graph drawing; graph embedding; crossing number; two-dimensional simplicial complex},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Německo},
   pages = {"21:1"-"21:18"},
   publisher = {Schloss Dagstuhl - Leibniz Center for Informatics},
   title = {A Unified FPT Framework for Crossing Number Problems},
   year = {2025}
}

TY  - CONF
ID  - 2561783
AU  - Colin de Verdière, Éric - Hliněný, Petr
PY  - 2025
TI  - A Unified FPT Framework for Crossing Number Problems
PB  - Schloss Dagstuhl - Leibniz Center for Informatics
CY  - Dagstuhl, Německo
KW  - computational geometry
KW  - fixed-parameter tractability
KW  - graph drawing
KW  - graph embedding
KW  - crossing number
KW  - two-dimensional simplicial complex
N2  - 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 ℤ_+ ∪ {∞}, 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.
ER  -

COLIN DE VERDIÈRE, Éric a Petr HLINĚNÝ. A Unified FPT Framework for Crossing Number Problems. Online. In \textit{33rd Annual European Symposium on Algorithms (ESA 2025)}. LIPIcs 351. Dagstuhl, Německo: Schloss Dagstuhl - Leibniz Center for Informatics, 2025, s.~''21:1''-''21:18'', 18 s. ISSN~1868-8969. Dostupné z: https://doi.org/10.4230/LIPIcs.ESA.2025.21.

Přehled o publikaci