Xuong tree


In graph theory, a Xuong tree is a spanning tree of a given graph with the property that, in the remaining graph, the number of connected components with an odd number of edges is as small as possible.
They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.
According to Xuong's results, if is a Xuong tree
and the numbers of edges in the components of are, then the maximum genus of an embedding of is.
Any one of these components, having edges, can be partitioned into edge-disjoint two-edge paths, with possibly one additional left-over edge.
An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one.
A Xuong tree, and a maximum-genus embedding derived from it, may be found in any graph in polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids.