Authors: I. Fabrici, J. Harant, S. Mohr, J.M. Schmidt Title: Longer cycles in essentially 4-connected planar graphs Source: Discussiones Mathematicae Graph Theory Received 16.10.2017, Revised 13.03.2018, Accepted 13.03.2018, doi: 10.7151/dmgt.2133 | |
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 °umference(G) of a longest cycle of any essentially 4-connected planar graph G on n vertices is at least \frac{2n+4}{5} and Fabrici, Harant and {Jendro{\ml}} improved this result to °umference(G)≥ \frac{1}{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 \frac{3}{5}(n+2) and that such a cycle can be found in time O(n^{2}). | |
Keywords: essentially 4-connected planar graph, longest cycle, circumference, shortness coefficient | |
Links: |