Metric uniformization and spectral bounds for graphs

DOI10.1007/s00039-011-0132-9zbMath1229.05094arXiv1008.3594OpenAlexW2963487913WikidataQ125324258 ScholiaQ125324258MaRDI QIDQ659931

Shang-Hua Teng, Gregory N. Price, James R. Lee, Jonathan A. Kelner

Publication date: 24 January 2012

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1008.3594

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Metric geometry (51F99) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) General theory of differentiable manifolds (58A99) Circle packings and discrete conformal geometry (52C26)

Related Items (10)

Multi-way dual Cheeger constants and spectral bounds of graphs ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Eigenvalues of the Laplacian on the Goldberg-Coxeter constructions for 3- and 4-valent graphs ⋮ Unnamed Item ⋮ Quasimetric embeddings and their applications ⋮ Conformal growth rates and spectral geometry on distributional limits of graphs ⋮ Separators in region intersection graphs ⋮ Discrete uniformizing metrics on distributional limits of sphere packings ⋮ Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs

Uses Software

• MESHPART

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds for eigenvalues of conformal metrics
• Graph minors. XX: Wagner's conjecture
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Spectral partitioning works: planar graphs and finite element meshes
• Eigenvalues and expanders
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Extending Lipschitz functions via random metric partitions
• Triangulations and moduli spaces of Riemann surfaces with group actions
• Measured descent: A new embedding method for finite metrics
• Graph minors. VIII: A Kuratowski theorem for general surfaces
• Divide-and-conquer approximation algorithms via spreading metrics
• Graph Coloring Using Eigenvalue Decomposition
• A separator theorem for graphs of bounded genus
• An extremal function for contractions of graphs
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• Diameters and Eigenvalues
• A Separator Theorem for Planar Graphs
• Finite-Difference Approach to the Hodge Theory of Harmonic Forms
• Eigenvectors of acyclic matrices
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Geometric Separators for Finite-Element Meshes
• Excluded minors, network decomposition, and multicommodity flow
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• An r-Dimensional Quadratic Placement Algorithm
• Lower Bounds for the Partitioning of Graphs
• Kreisausfüllungen der hyperbolischen Ebene
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Metric uniformization and spectral bounds for graphs