Longer Cycles in Essentially 4-Connected Planar Graphs

Abstract

A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at least one of the two components of G − S is an isolated vertex. Jackson and Wormald proved that the length circ(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least 2n+45{{2n + 4} \over 5} and Fabrici, Harant and Jendrol’ improved this result to circ(G)≥12(n+4){\rm{circ}} ( G ) \ge {1 \over 2} ( {n + 4} ) . In the present paper, we prove that an essentially 4-connected planar graph on n vertices contains a cycle of length at least 35(n+2){3 \over 5} ( {n + 2} ) and that such a cycle can be found in time O(n2).

Keywords

• essentially 4-connected planar graph
• longest cycle
• circumference
• shortness coefficient
• 05c38
• 05c10