Xuong tree

In graph theory, a Xuong tree is a spanning tree

with the property that, in the remaining graph

, the number of connected components with an odd number of edges is as small as possible.

[1] They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.

is a Xuong tree and the numbers of edges in the components of

, then the maximum genus of an embedding of

edges, can be partitioned into

edge-disjoint two-edge paths, with possibly one additional left-over edge.

[3] 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.

[1][2] 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.