Finding thet-join structure of graphs

t-joins are generalizations of postman tours, matchings, and paths;t-cuts contain planar multicommodity flows as a special case. In this paper we present a polynomial time combinatorial algorithm that determines a minimumt-join and a maximum packing oft-cuts and that ends up with a Gallai-Edmonds type structural decompostion of (G, t) pairs, independent of the running of the algorithm. It only uses simple combinatorial steps such as the symmetric difference of two sets of edges and does not use any shrinking operations.