On the Fiedler value of large planar graphs (Extended abstract)

The Fiedler value λ 2 , also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study upper bounds on the Fiedler value of planar graphs. Let λ 2 max be the maximum Fiedler value among all planar graphs G with n vertices. We show here the bounds 2 + Θ ( 1 n 2 ) ⩽ λ 2 max ⩽ 2 + O ( 1 n ) . Similar lower and upper bounds on the maximum Fiedler value are obtained for the classes of bipartite planar graphs, bipartite planar graphs with minimum vertex degree 3 and outerplanar graphs. We also derive almost tight bounds on λ 2 max for the classes of graphs of bounded genus and K h -minor-free graphs. oofs rely on a result of Spielman and Teng stating that λ 2 ⩽ 8 Δ n for any planar graph with n vertices and maximum vertex degree Δ, on a result of Kelner stating that λ 2 = O ( g n ) for genus g graphs of bounded degree, and on the separator theorem.