Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus

DOI10.1137/S0097539705447244zbMath1096.05048MaRDI QIDQ5470718

Jonathan A. Kelner

Publication date: 1 June 2006

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

circle packingLaplaciangraph separatorsbounded genusspectral partitioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Spectral concentration and greedy \(k\)-clustering ⋮ Approximation algorithms via contraction decomposition ⋮ Expander graphs, gonality, and variation of Galois representations ⋮ On the Fiedler value of large planar graphs ⋮ Metric uniformization and spectral bounds for graphs ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Eigenvalues of the Laplacian on the Goldberg-Coxeter constructions for 3- and 4-valent graphs ⋮ Unnamed Item ⋮ Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs ⋮ Short and Simple Cycle Separators in Planar Graphs

This page was built for publication: Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus