Longer cycles in essentially 4-Connected planar graphs

Publikationstyp
Journal Article
Date Issued
2020
Sprache
English
Author(s)
Fabrici, Igor  
Harant, Jochen  
Mohr, Samuel  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7595
Journal
Discussiones mathematicae  
Volume
40
Issue
1
Start Page
269
End Page
277
Citation
Discussiones Mathematicae Graph Theory (2020)
Publisher DOI
10.7151/dmgt.2133
Publisher Link
http://arxiv.org/abs/1710.05619v1
Scopus ID
2-s2.0-85078119070
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²).
Subjects
circumference
essentially 4-connected planar graph
longest cycle
shortness coefficient
Mathematics - Combinatorics
Mathematics - Combinatorics
Computer Science - Discrete Mathematics
05C38, 05C10
DDC Class
600: Technology