Abstract   A planar 3-connected graph  G  is essentially 4-connected if, for any 3-separator  S  of  G , one component of the graph obtained from  G  by removing  S  is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on  n  vertices contains a cycle  C  such that   |  V  (  C  )  |  ≥    2  n  +  4   5   . For a cubic essentially 4-connected planar graph  G , Grunbaum with Malkevitch, and Zhang showed that  G  has a cycle on at least     3   4   n   vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of  G  are presented if  G  is an essentially 4-connected planar graph of maximum degree 4 or  G  is an essentially 4-connected maximal planar graph.
['Jochen Harant', 'Igor Fabrici', 'Stanislav Jendrol']
On Longest Cycles in Essentially 4-connected Planar Graphs