Lower Bounds for Strictly Fundamental Cycle Bases in Grid Graphs

such that the sum of the lengths of its induced fundamental
circuits is as small as possible. We motivate why planar
square grid graphs are very relevant instances for this
problem. In particular, other contributions already showed
that the identification of strong lower bounds is highly
challenging.

Asymptotically, for a graph on $n$~vertices,
Alon et al. (1995) obtained a lower bound of $\Omega(n \log{n})$.
We raise the n log n coefficient by a factor of 325.
Concerning optimality proofs, the largest grid for which provably
optimum solutions were known is 6x6, and it was obtained
by massive MIP computing power. Here, we present a combinatorial
optimality proof even for the 8x8-grid. These two results
are complemented by new combinatorial lower bounds for the
dimensions in which earlier empirical computations were performed,
i.e., for up to 10,000 vertices.

(Joint work with E. Köhler, R. Rizzi, G. Wünsch.)