  We show how to find and efficiently maintain maximal k-edge-connected
subgraphs in undirected graphs. In particular, we provide the following
results. (1) A general framework for maintaining the maximal k-edge-connected
subgraphs upon insertions of edges or vertices, by successively partitioning
the graph into its k-edge-connected components. This defines a decomposition
tree, which can be maintained by using algorithms for the incremental
maintenance of the k-edge-connected components as black boxes at every level of
the tree. (2) As an application of this framework, we provide two algorithms
for the incremental maintenance of the maximal $3$-edge-connected subgraphs.
These algorithms allow for vertex and edge insertions, interspersed with
queries asking whether two vertices belong to the same maximal
$3$-edge-connected subgraph. The first algorithm has $O(m\alpha(m,n) +
n^2\log^2 n)$ total running time and uses $O(n)$ space, where $m$ is the number
of edge insertions and queries, and $n$ is the total number of vertices
inserted. The second algorithm performs the same operations in faster
$O(m\alpha(m,n) + n^2\alpha(n,n))$ time in total, using $O(n^2)$ space. (3) We
provide efficient constructions of sparse subgraphs that have the same maximal
k-edge-connected subgraphs as the original graph. These are useful in speeding
up computations involving the maximal k-edge-connected subgraphs in dense
undirected graphs. (4) We give two deterministic algorithms for computing the
maximal k-edge-connected subgraphs in undirected graphs, with running times
$O(m+k^{O(1)}n\sqrt{n}\mathrm{polylog}(n))$ and
$O(m+k^{O(k)}n\sqrt{n}\log{n})$, respectively. (5) A fully dynamic algorithm
for maintaining information about the maximal k-edge-connected subgraphs for
fixed k. Our update bounds are $O(n\sqrt{n}\log{n})$ worst-case time, and we
achieve constant time for maximal k-edge-connected subgraph queries.
