  The Gomory-Hu tree, or a cut tree, is a classic data structure that stores
minimum $s$-$t$ cuts of an undirected weighted graph for all pairs of nodes
$(s,t)$. We propose a new approach for computing the cut tree based on a
reduction to the problem that we call OrderedCuts. Given a sequence of nodes
$s,v_1,\ldots,v_\ell$, its goal is to compute minimum
$\{s,v_1,\ldots,v_{i-1}\}$-$v_i$ cuts for all $i\in[\ell]$. We show that the
cut tree can be computed by $\tilde O(1)$ calls to OrderedCuts. We also
establish new results for OrderedCuts that may be of independent interest.
First, we prove that all $\ell$ cuts can be stored compactly with $O(n)$ space
in a data structure that we call an OC tree. We define a weaker version of this
structure that we call depth-1 OC tree, and show that it is sufficient for
constructing the cut tree. Second, we prove results that allow
divide-and-conquer algorithms for computing OC tree. We argue that the
existence of divide-and-conquer algorithms makes our new approach a good
candidate for a practical implementation.
