  Given a connected undirected graph G = [V; E] where |E| =2(|V| -1), we
present two algorithms to check if G can be decomposed into two edge disjoint
spanning trees, and provide such a decomposition when it exists. Unlike
previous algorithms for finding edge disjoint spanning trees in general
undirected graphs, based on matroids and complex in description, our algorithms
are based on simple graph reduction techniques and thus easy to describe and
implement. Moreover, the running time for our solutions is asymptotically
faster. Specifically, ours are the first algorithms to achieve a running time
that is a polylog factor from linear, approaching the 1974 linear time
algorithm of Robert E. Tarjan for directed graphs. A direct implication of our
result is that minimally rigid graphs, also called Laman graphs, can be
recognized in almost linear time, thus answering a long standing open problem.
