Abstract
In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T, there exists a sequence of fundamental cycles C 1,C 2,…,C 2g with C 2i−1 ∩ C 2i ≠ /0 for 1 ⩽ i ⩽ g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C 1, C 2,…,C 2γM(G) such that C 2i−1 ∩ C 2i ≠ /0 for 1 ⩽ i ⩽ γM (G), where β(G) and γM (G) are the Betti number and the maximum genus of G, respectively. This implies that it is possible to construct an orientable embedding with large genus of a graph G from an arbitrary spanning tree T (which may have very large number of odd components in G E(T)). This is different from the earlier work of Xuong and Liu, where spanning trees with small odd components are needed. In fact, this makes a common generalization of Xuong, Liu and Fu et al. Furthermore, we show that (1) this result is useful for locating the maximum genus of a graph having a specific edge-cut. Some known results for embedded graphs are also concluded; (2) the maximum genus problem may be reduced to the maximum matching problem. Based on this result and the algorithm of Micali-Vazirani, we present a new efficient algorithm to determine the maximum genus of a graph in \( O((\beta (G))^{\frac{5} {2}} ) \) steps. Our method is straight and quite different from the algorithm of Furst, Gross and McGeoch which depends on a result of Giles where matroid parity method is needed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bondy J A, Murty U S R. Graph Theory with Application. London: MacMillan, 1976
Liu Y P. The maximum orientable genus of a graph. Scientia Sinica, Special Issue on Math II, 41–55 (1979)
Mohar B, Thomassen C. Graphs on Surfaces. Maryland: Johns Hopkins University Press, 2001
Xoung N H. How to determine the maximum genus of a graph. J Combin Theory Ser B, 26: 217–225 (1979)
Fu H L, Skoviera M, Tsai M. The maximum genus, matchings and the cycle space of a graph. Csechoslovak Math J, 48(123): 329–339 (1998)
Huang Y. Maximum genus of a graph in term of its embedding properties. Discrete Math, 262: 171–180 (2003)
Micali S, Vazirani V V. An \( O(\sqrt {\left| V \right|} \left| E \right|) \) algorithm for finding maximum matching in general graphs. In: Proc. 21st IEEE Symp Found Comp Sci, New York: ACM Press, 1980, 17–27
Furst M L, Gross J L, McGeoch L A. Finding a maximum-genus graph imbedding. J Assoc Comput Mach, 35: 523–534 (1988)
Giles R. Optimum matching forest I: Special weights. Math Program, 22: 1–11 (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by National Natural Science Foundation of China (Grant Nos. 10271048, 10671073), Science and Technology Commission of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Discipline Project (Project No. B407)
Rights and permissions
About this article
Cite this article
Ren, H., Zhao, H. & Li, H. Fundamental cycles and graph embeddings. Sci. China Ser. A-Math. 52, 1920–1926 (2009). https://doi.org/10.1007/s11425-009-0041-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-009-0041-7