Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433765 | Theoretical Computer Science | 2016 | 9 Pages |
Let G be a 3-connected planar graph with n vertices and let p(G)p(G) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p(G)≥logn12loglogn. To demonstrate the tightness of this bound, we notice that the above inequality implies p(G)∈Ω((log2n)1−ε)p(G)∈Ω((log2n)1−ε), where ε is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p(G)∈O(logn)p(G)∈O(logn). As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least n3 vertices. The proofs in the paper are constructive and give rise to O(n)O(n)-time algorithms.