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 λ2max be the maximum Fiedler value among all planar graphs G with n vertices. We show here the bounds 2+Θ(1n2)⩽λ2max⩽2+O(1n). 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 λ2max for the classes of graphs of bounded genus and Kh-minor-free graphs.The proofs 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(gn) for genus g graphs of bounded degree, and on the separator theorem.