The Genus of a Graph: A Survey
Liangxia Wan · Symmetry · 2023
The problem of determining the genus for a graph can be dated to the Map Color Conjecture proposed by Heawood in 1890. This was implied to be a Thread Problem by Hilbert and Cohn-Vossen. The conjecture was finally established by Ringel, Youngs, and many other mathematicians. Subsequently, the genera of some special graphs with symmetry were determined. The study of genus embeddings of graphs is closely related to other invariants of a graph. Specifically, the computational complexity is dependent on the genus of the underlying graph for certain well-known NP-hard problems. In this survey, main construction techniques and certain criteria are stated in the topic of the genus of a graph. Most graphs with a known genus are listed. A new theorem is shown that the method of joint trees of a graph is reasonable. Moreover, a formal set is introduced, and related results are obtained. Although a cubic graph of Hamilton cycle is asymmetric, it is interesting that a set of associate surfaces of all its joint trees is a formal set with symmetry.