Parametric Minimum Spanning Trees and Constructive Solid Geometry

David Eppstein, ICS, UC Irvine

In this talk I describe ongoing work on my attempts to improve this lower bound. Instead of considering the minimum spanning tree itself, I consider the quantity

Geometrically, the shape formed by plotting *q*(*x*)
against *x* is a lower envelope (min) of an upper envelope
(max) of certain sets of lines (plots of each individual edge
weight). The upper envelope of lines is a concave chain, so *
q*(*x*) is the lower envelope of certain concave chains. It
forms a monotone path in the line arrangement (monotone simply
means that it is the plot of a function, having only one
intersection with any vertical line). The convex vertices in this
path correspond to minimum spanning tree changes, although the
concave vertices may not.

My first attempt to prove a better lower bound on the number of
minimum spanning trees starts from a construction of Matousek, who
showed that monotone paths in arrangements may have complexity
Omega(*m*^{5/3}) (no nontrivial upper bound is known).
Since Matousek's lower bound on monotone paths is larger than our
known upper bound on minimum spanning trees, there are some
monotone paths that do not correspond to minimum spanning tree
sequences. I tried a simplified example in which *m* lines are
partitioned into sqrt *m* "cables" of sqrt *m*
lines each, with an additional *m* lines connecting up the
intersections of pairs of cables in such a way that each
intersection contributes sqrt *m* vertices (both convex
and concave) to the monotone path. It is possible to represent this
monotone path as a lower envelope of a simple family of concave
chains, however when I tried to translate this family back into
graph-theoretic terms I ended up with "coat-hangers" (triangles
with a dangling edge) instead of paths.

Instead, I tried restricting the problem further, to paths in
series-parallel graphs. Series composition corresponds to forming
*q*(*x*) as the upper envelope of two paths coming from
the two subgraphs being composed, and parallel composition
corresponds to a lower envelope. Therefore, one can re-interpret
the problem as a form of "constructive solid geometry" for monotone
paths: one is given a set of monotone paths, initially just *
m* lines, and can repeatedly perform operations that combine two
paths, replacing the two by a single upper or lower envelope. How
complex a path can result from this process? The bounds I currently
know are exactly those for the original parametric MST problem,
Omega(*m* alpha(*n*)) and
O(*m* sqrt *n*).

In summary, I still haven't made progress in narrowing the gap between lower and upper bounds for parametric MSTs, but at least I've found some interesting ways of translating the problem into some geometric formulations that don't look like they should have anything to do with MSTs.