On the Fiedler value of large planar graphs

International audienceThe Fiedler value λ_2, also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs G with n vertices, denoted by λ_2max, and we show the bounds 2+\Theta(1/n^2) \leq λ_2max \leq 2+O(1/n). We also provide bounds on the maximum Fiedler value for the following classes of planar graphs: Bipartite planar graphs, bipartite planar graphs with minimum vertex-degree 3, and outerplanar graphs. Furthermore, we derive almost tight bounds on λ_2max for two more classes of graphs, those of bounded genus and K_h-minor-free graphs