[MACSMIN] Mysteries about crossing numbers

8^th September 2025, 09:00 Materials Innovation Factory, Liverpool, UK
Janos Pach
Rényi Institute, Budapest and EPFL, Lausanne

Abstract

For any graph G, the crossing number cr(G) of G is defined as the smallest number k such that G can be drawn in the plane with k crossing points between its edges. The pairwise crossing number pair-cr(G) of G is defined in a similar way, except that in this case we want to minimize the number of crossing pairs of edges. Obviously, pair-cr(G) is at most cr(G). It is one of the most annoying unsolved problems for graph embeddings whether there exists a graph for which these two parameters do not coincide. Since computing these parameters are NP-complete problems, it is difficult to test the inequality even for small graphs. After giving a whirlwind survey of the topic, we discuss some recent develop.

This talk is not a standard seminar talk and is part of the MACSMIN workshop (https://kurlin.org/macsmin/2025.php).
Advertised at the request of Vitaliy Kurlin