Showing cs.CGShow all
2 papers · 1 filter
cs.CG2024
A Unified FPT Framework for Crossing Number Problems
Éric Colin de Verdière, Petr Hliněný
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 fr…
cs.CG2024
Crossing Number is NP-hard for Constant Path-width (and Tree-width)
Petr Hliněný, Liana Khazaliya
The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem,…