Mónika Csikós 

Title: An improved algorithm to construct spanning paths with low crossing numbers

Abstract: Given a hypergraph $H = (V,\mathcal E)$, we consider the problem of finding a spanning path of $V$ such that each hyperedge in $\mathcal E$ crosses few edges of the path (we say that a hyperedge $h \in \mathcal E$ crosses the edge $\{x,y\}$ iff $|h \cap \{x,y\} | = 1$). This structure was originally introduced for geometric range searching in the 1980s and has found applications in various fields, including algorithmic graph theory and combinatorial data approximation.
The seminal work of Chazelle and Welzl (1989) provided an algorithm that for any hypergraph with $n$ vertices, $m$ edges, and dual VC-dimension $d$, constructs a spanning path with crossing number $O(n^{1 - 1/d})$ in time $O(n^3 m)$. Since then, despite several advances for geometric hypergraphs, the general algorithm for abstract hypergraphs remained unimproved.
We propose a new sampling-based algorithm which is applicable to any finite hypergraph with dual VC-dimension $d$ and provides a spanning path with expected crossing number $O(n^{1-1/d})$ in time $O(n^{1/d} m + n^{2 + 1/d})$ resulting in an $n^{2-1/d}$ factor speed-up on the construction time (assuming $m \geq n$). Joint work with Nabil H. Mustafa.