Upper and Lower Bounds on Long Dual-Paths in Line Arrangements

Udo Hoffmann, Linda Kleist, Tillmann Miltzow

Given a line arrangement $\mathcal{A}$ with $n$ lines, we show that there exists a path of length $n^2/3-O(n)$ in the dual graph of $\mathcal{A}$ formed by its faces. This bound is tight u…