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)nlog2/log3.

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)|.