###### Options

# Longer cycles in essentially 4-Connected planar graphs

Publikationstyp

Journal Article

Publikationsdatum

2020

Sprache

English

TORE-URI

Enthalten in

Volume

40

Issue

1

Start Page

269

End Page

277

Citation

Discussiones Mathematicae Graph Theory (2020)

Publisher DOI

Publisher Link

Scopus ID

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+4/5) and Fabrici, Harant and Jendrol' improved this result to circ(G)≥ ½(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 ⅗(n+2) and that such a cycle can be found in time O(n²).