  A flow graph $G=(V,E,s)$ is a directed graph with a distinguished start
vertex $s$. The dominator tree $D$ of $G$ is a tree rooted at $s$, such that a
vertex $v$ is an ancestor of a vertex $w$ if and only if all paths from $s$ to
$w$ include $v$. The dominator tree is a central tool in program optimization
and code generation and has many applications in other diverse areas including
constraint programming, circuit testing, biology, and in algorithms for graph
connectivity problems. A low-high order of $G$ is a preorder $\delta$ of $D$
that certifies the correctness of $D$ and has further applications in
connectivity and path-determination problems. In this paper, we first consider
how to maintain efficiently a low-high order of a flow graph incrementally
under edge insertions. We present algorithms that run in $O(mn)$ total time for
a sequence of $m$ edge insertions in an initially empty flow graph with $n$
vertices.These immediately provide the first incremental certifying algorithms
for maintaining the dominator tree in $O(mn)$ total time, and also imply
incremental algorithms for other problems. Hence, we provide a substantial
improvement over the $O(m^2)$ simple-minded algorithms, which recompute the
solution from scratch after each edge insertion. We also show how to apply
low-high orders to obtain a linear-time $2$-approximation algorithm for the
smallest $2$-vertex-connected spanning subgraph problem (2VCSS). Finally, we
present efficient implementations of our new algorithms for the incremental
low-high and 2VCSS problems and conduct an extensive experimental study on
real-world graphs taken from a variety of application areas. The experimental
results show that our algorithms perform very well in practice.
