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.
Lower and upper bounds for long induced paths in 3-connected planar graphs
DI GIACOMO, Emilio
;LIOTTA, Giuseppe;
2016
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
