Name
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 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) >= 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 3/5 (n + 2) and that such a cycle can be found in time O(n(2)). |
Year | DOI | Venue |
|---|---|---|
2020 | 10.7151/dmgt.2133 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | DocType | Volume |
essentially 4-connected planar graph,longest cycle,circumference,shortness coefficient | Journal | 40 |
Issue | ISSN | Citations |
1 | 1234-3099 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Fabrici | 1 | 101 | 14.64 |
| Jochen Harant | 2 | 217 | 30.62 |
| Samuel Mohr | 3 | 0 | 0.34 |
| Jens M. Schmidt | 4 | 0 | 0.34 |