# On the Circumference of Essentially 4-connected Planar Graphs

## DOI:

https://doi.org/10.7155/jgaa.00516## Keywords:

Circumference , Essentially 4-Connected Planar Graphs , Longest Cycle , Discharging , Tutte Cycle## Abstract

A planar graph is*essentially $4$-connected*if it is 3-connected and every of its 3-separators is the neighborhood of a single vertex. Jackson and Wormald proved that every essentially 4-connected planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{2n+4}{5}$, and this result has recently been improved multiple times. In this paper, we prove that every essentially 4-connected planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{5}{8}(n+2)$. This improves the previously best-known lower bound $\frac{3}{5}(n+2)$.

### Downloads

Download data is not yet available.

## Downloads

## Published

2020-01-01

## How to Cite

*Journal of Graph Algorithms and Applications*,

*24*(1), 21–46. https://doi.org/10.7155/jgaa.00516

## License

Copyright (c) 2020 Igor Fabrici, Jochen Harant, Samuel Mohr, Jens Schmidt

This work is licensed under a Creative Commons Attribution 4.0 International License.