The problem I've run into is the following:
We have a graph G in which the weights of its edges are upward parabolas varying in time. For each instant t, we could potentially calculate the Minimum Spanning Tree. Since parabolas are convex and MST(t) is a minimisation problem we can try to find the 'global' MST: from all the infinetely many times t choose the MST(t) with minimal weight.
I've found an E3·log(V) algorithm: two parabolas meet at most 2 times, thus the numbers of crossings of all weight parabolas is E(E - 1) = O(E2). At all times between two consecutive crossings the order of the edges is the same; therefore the MST will be the same. Thus, we can compute it using Kruskal in O(E·logV) and then minimize for the edges found in O(V).
Can you find a faster solution? [I don't know if it exists :) ]