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]

References

1. Beineke, Lowell W.; Wilson, Robin J. (2009), Topics in topological graph theory, Encyclopedia of Mathematics and its Applications, vol. 128, Cambridge University Press, Cambridge, p. 36, doi:10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, MR 2581536
2. Xuong, Nguyen Huy (1979), "How to determine the maximum genus of a graph", Journal of Combinatorial Theory, Series B, 26 (2): 217–225, doi:10.1016/0095-8956(79)90058-3, MR 0532589
3. Sumner, David P. (1974), "Graphs with 1-factors", Proceedings of the American Mathematical Society, 42 (1), American Mathematical Society: 8–12, doi:10.2307/2039666, JSTOR 2039666, MR 0323648
4. Furst, Merrick L.; Gross, Jonathan L.; McGeoch, Lyle A. (1988), "Finding a maximum-genus graph imbedding", Journal of the ACM, 35 (3): 523–534, doi:10.1145/44483.44485, MR 0963159, S2CID 17991210