Parameterised Algorithms for Book Drawings with Crossing Minimization

Parameterised Algorithms for Book Drawings with Crossing Minimization

Mathematics

October 2026

Vladimir Brankovic

A k-page book consists of a straight line, called the spine, and k half-planes, called pages, sharing the spine as their boundary. A k-page book drawing of a graph G places the vertices on the spine and draws each edge on a single page. The k-page crossing number is the minimum number of edge crossings over all possible k-page drawings. Finding a crossing-free book drawing with minimum number of pages(Book Thickness) and minimizing crossings for a fixed k (Book Drawing With Crossing Minimization) are both NP-hard. Recent works established fixed-parameter algorithms for Book Thickness parameterized by the vertex cover number and the vertex integrity, respectively [1, 2]. In this paper, we present the main ideas of these works and derive separate fixed-parameter algorithms for Book Drawing with Crossing Minimization w.r.t. the vertex cover number and the vertex integrity number.

Mathematics, Computer Science, Combinatorics, Embedding, Parameterised Algorithms, Book Thickness, Crossing, Minimization, Vertex Cover, Vertex Integrity