Crossing Numbers of Graphs

Crossing Numbers of Graphs is a book in mathematics, on the minimum number of edge crossings needed in graph drawings. It was written by Marcus Schaefer, a professor of computer science at DePaul University, and published in 2018 by the CRC Press in their book series Discrete Mathematics and its Applications.

Topics

The main text of the book has two parts, on the crossing number as traditionally defined and on variations of the crossing number, followed by two appendices providing background material on topological graph theory and computational complexity theory.

After introducing the problem, the first chapter studies the crossing numbers of complete graphs (including Hill's conjectured formula for these numbers) and complete bipartite graphs (Turán's brick factory problem and the Zarankiewicz crossing number conjecture), again giving a conjectured formula). It also includes the crossing number inequality, and the Hanani–Tutte theorem on the parity of crossings. The second chapter concerns other special classes of graphs including graph products (especially products of cycle graphs) and hypercube graphs. After a third chapter relating the crossing number to graph parameters including skewness, bisection width, thickness, and (via the Albertson conjecture) the chromatic number, the final chapter of part I concerns the computational complexity of finding minimum-crossing graph drawings, including the results that the problem is both NP-complete and fixed-parameter tractable.

In the second part of the book, two chapters concern the rectilinear crossing number, describing graph drawings in which the edges must be represented as straight line segments rather than arbitrary curves, and Fáry's theorem that every planar graph can be drawn without crossings in this way. Another chapter concerns 1-planar graphs and the associated local crossing number, the smallest number k such that the graph can be drawn with at most k crossings per edge. Two chapters concern book embeddings and string graphs, and two more chapters concern variations of the crossing number that count crossings in different ways, for instance by the number of pairs of edges that cross or that cross an odd number of times. The final chapter of part II concerns thrackles and the problem of finding drawings with a maximum number of crossings.

Audience and reception

The book can be used as an advanced textbook, and has exercises provided for that use. However, it assumes that its readers are already familiar with both graph theory and the design and analysis of algorithms. Reviewing the book, L. W. Beineke calls it a "valuable contribution" for its presentation of the many results in this area.