Maximum Genus and 1-Factors of Near-Triangulation Graphs
LU Chang-qing, Han Ren · Huadong Shifan Daxue xuebao. Ziran kexue ban · 2006
This paper proved that if the geometric dual G* of a near-triangulation plane graph G contains a set of [1/2φ] independent edges, then the maximum genusγM(G) of G is at least [1/2β(G)] - 1, whereφandβ(G) represent the number of faces of plane G and the Betti number of G. In particular,γM(G) = 1/2β(G)ifφ= 0 mod 2. As applications, several known results are presented.