graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a Xuong tree is a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

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 Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial n ...

. 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

\textstyle\sum_^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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, by a transformation to a more general computational problem on

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

s, the

matroid parity problem In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection ...

for

linear matroid In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of repre ...

References

{{reflist, refs= {{citation , last1 = Beineke , first1 = Lowell W. , author1-link = L. W. Beineke , last2 = Wilson , first2 = Robin J. , author2-link = Robin Wilson (mathematician) , doi = 10.1017/CBO9781139087223 , isbn = 978-0-521-80230-7 , mr = 2581536 , page = 36 , publisher = Cambridge University Press, Cambridge , series = Encyclopedia of Mathematics and its Applications , title = Topics in topological graph theory , volume = 128 , year = 2009 {{citation , last1 = Furst , first1 = Merrick L. , last2 = Gross , first2 = Jonathan L. , last3 = McGeoch , first3 = Lyle A. , doi = 10.1145/44483.44485 , issue = 3 , journal =

Journal of the ACM The ''Journal of the ACM'' is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief An editor-in-c ...

, mr = 963159 , pages = 523–534 , title = Finding a maximum-genus graph imbedding , volume = 35 , year = 1988, s2cid = 17991210 {{Citation , last = Sumner , first = David P. , authorlink = David Sumner , doi = 10.2307/2039666 , mr = 0323648 , journal = Proceedings of the American Mathematical Society , pages = 8–12 , title = Graphs with 1-factors , volume = 42 , year = 1974 , issue = 1 , publisher = American Mathematical Society , jstor = 2039666 {{citation , last = Xuong , first = Nguyen Huy , doi = 10.1016/0095-8956(79)90058-3 , hdl = , issue = 2 , journal = Journal of Combinatorial Theory , mr = 532589 , pages = 217–225 , series = Series B , title = How to determine the maximum genus of a graph , volume = 26 , year = 1979, doi-access = free Spanning tree Topological graph theory