1. Lower and upper bounds for long induced paths in 3-connected planar graphs.
- Author
-
Di Giacomo, Emilio, Liotta, Giuseppe, and Mchedlidze, Tamara
- Subjects
- *
MATHEMATICAL bounds , *PLANAR graphs , *PATHS & cycles in graph theory , *GEOMETRIC vertices , *MATHEMATICAL inequalities , *SUBGRAPHS - Abstract
Let G be a 3-connected planar graph with n vertices and let 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 n 12 log log n . To demonstrate the tightness of this bound, we notice that the above inequality implies p ( G ) ∈ Ω ( ( log 2 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 ) . 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 n 3 vertices. The proofs in the paper are constructive and give rise to O ( n ) -time algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF