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

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. We prove that p(G)≥logn12loglogn . To demonstrate the tightness of this bound, we notice that the above inequality implies p(G) ∈ Ω((log2 n)1 − ε ), where ε is any positive constant smaller than 1, and describe an infinite family of 3-connected planar graphs for which 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 n√3 vertices. The proofs in the paper are constructive and give rise to O(n)-time algorithms.
2013
9783642450426
9783642450433
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1173281
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact