Lower and upper bounds for long induced paths in 3-connected planar graphs

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)≥log⁡n12log⁡log⁡n. To demonstrate the tightness of this bound, we notice that the above inequality implies p(G)∈Ω((log2⁡n)1−ε)p(G)∈Ω((log2⁡n)1−ε), where ε   is any positive constant smaller than 1, and describe an infinite family of planar graphs for which p(G)∈O(log⁡n)p(G)∈O(log⁡n). 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.