Xuong tree

In graph theory, a Xuong tree is a spanning tree $T$ of a given graph $G$ with the property that, in the remaining graph $G-T$, 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.

A Xuong tree. Only one component of the non-tree edges (the red component) has an odd number of edges, the minimum possible for this graph.

According to Xuong's results, if $T$ is a Xuong tree and the numbers of edges in the components of $G-T$ are $m_{1},m_{2},\dots ,m_{k}$, then the maximum genus of an embedding of $G$ is $\textstyle \sum _{i=1}^{k}\lfloor m_{i}/2\rfloor$. Any one of these components, having $m_{i}$ edges, can be partitioned into $\lfloor m_{i}/2\rfloor$ 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.