Search

A subcubic planar graph is a planar graph whose vertices have degree at most 3. We show that the subcubic planar graphs with at least five vertices have planar slope number at most 4, which is worst-case optimal. This answers an open question by Jelínek et al. [10] . Furthermore, we prove that the subcubic planar graphs with at least five vertices have angular resolution π / 4 , which solves an open problem by Kant [11] and by Formann et al. [8] . [ABSTRACT FROM AUTHOR]

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]