tree/cotree extraction

All,

A colleague of mine inquired about algorithms for extracting
trees and cotrees from a graph.  After some clarification,
his conditions and requirements appear to be:

1. the graph results from a finite element dicredtization of a 3D pde;
   the graph is irregular---some nodes have more edges connected to
   them than others;

2. he's interested in practice, not theory;

3. the tree should have "branches that are about the same size,"
   by which I believe he means for any node in the tree, the
   subtree rooted at the node's children should contain approximately
   the same number of nodes (i.e., balanced tree);

4. he's looking for a sequential algorithm, but will eventually
   be interested in a parallel algorithm; at present he's working
   with 0.5 billion nodes;

5. there is no restriction on choosing the root node;

6. I'm guessing the tree should be as bushy as possible
   so as to minimize the distance from the root to leaf nodes.

I immediately thought of breadth first search, but don't know
about dealing with requirements (3) and (6).  I suspect one would want
to start by finding a "centermost" node and using that as the root.

Any thoughts or references on these issues would be greatly appreciated.

thanks,
David Hysom
Center for Advanced Scientific Computing
Lawrence Livermore Nat. Lab.