Xuong tree

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.

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.Template:R They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.Template:R

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 ${\sum }_{i=1}^k\lfloor m_i/2\rfloor$.Template:R 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.Template:R 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.Template:R

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.Template:R