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 of a given graph 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.[2]

According to Xuong's results, if is a Xuong tree and the numbers of edges in the components of are , then the maximum genus of an embedding of is .[1][2] Any one of these components, having 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.[1][4]


  1. ^ a b c d Beineke, Lowell W.; Wilson, Robin J. (2009), Topics in topological graph theory, Encyclopedia of Mathematics and its Applications, 128, Cambridge University Press, Cambridge, p. 36, doi:10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, MR 2581536
  2. ^ a b c 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, hdl:10338.dmlcz/101776, MR 0532589
  3. ^ Sumner, David P. (1974), "Graphs with 1-factors", Proceedings of the American Mathematical Society, American Mathematical Society, 42 (1): 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