Long Cycles in Graphs on a Fixed Surface

We prove that there exists a function a: N0×R+→N such that (i) If G is a 4-connected graph of order n embedded on a surface of Euler genus g such that the face-width of G is at least a(g, ε), then G can be covered by two cycles each of which has length at least (1−ε) n. We apply this to derive lower bounds for the length of a longest cycle in a graph G on any fixed surface. Specifically, there exist functions b: N0→N and c: N0→R+ such that for every graph G on n vertices that is embedded on a surface of Euler genus g the following statements hold: (ii) If G is 4-connected, then G contains a collection of at most b(g) paths which cover all vertices of G, and G contains a cycle of length at least n/b(g). (iii) If G is 3-connected, then G contains a cycle of length at least c(g) nlog 2/log 3. Moreover, for each ε>0, every 4-connected graph G with sufficiently large face-width contains a spanning tree of maximum degree at most 3 and a 2-connected spanning subgraph of maximum degree at most 4 such that the number of vertices of degree 3 or 4 in either of these subgraphs is at most ε |V(G)|.