Xuong tree

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

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