Boundaries of planar graphs, via circle packings

DOI10.1214/15-AOP1014MaRDI QIDQ726798zbMATH OpenFDO

Authors Omer Angel, Martin T. Barlow, Ori Gurel-Gurevich, Asaf Nachmias

Publication date 14 July 2016

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.3363, https://projecteuclid.org/euclid.aop/1463410036

zbMATH Keywords

random walkPoisson boundaryhyperbolicplanar graphcircle packingmartin boundary

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random walks on graphs (05C81)

Abstract: We provide a geometric representation of the Poisson and Martin boundaries of a transient, bounded degree triangulation of the plane in terms of its circle packing in the unit disc. (This packing is unique up to M"obius transformations.) More precisely, we show that any bounded harmonic function on the graph is the harmonic extension of some measurable function on the boundary of the disk, and that the space of extremal positive harmonic functions, that is, the Martin boundary, is homeomorphic to the unit circle. All our results hold more generally for any "good"-embedding of planar graphs, that is, an embedding in the unit disc with straight lines such that angles are bounded away from $0$ and $pi$ uniformly, and lengths of adjacent edges are comparable. Furthermore, we show that in a good embedding of a planar graph the probability that a random walk exits a disc through a sufficiently wide arc is at least a constant, and that Brownian motion on such graphs takes time of order $r^2$ to exit a disc of radius $r$. These answer a question recently posed by Chelkak (2014).

Recommendations

• Boundaries of planar graphs: a unified approach
• Circle boundaries of planar graphs
• Harmonic functions on planar and almost planar graphs and manifolds, via circle packings
• Harmonic Dirichlet functions on planar graphs
• The boundary of a square tiling of a graph coincides with the Poisson boundary

Cites work

• scientific article; zbMATH DE number 2182144 (Why is no real title available?)
• scientific article; zbMATH DE number 3934148 (Why is no real title available?)
• scientific article; zbMATH DE number 3549930 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• A boundary Harnack principle in twisted Hölder domains
• Analysis on local Dirichlet spaces. III: The parabolic Harnack inequality
• Aspects of Sobolev-type inequalities
• BOUNDARY THEORY OF MARKOV PROCESSES (THE DISCRETE CASE)
• Boundary Harnack principle and Martin boundary for a uniform domain
• Boundary behavior of harmonic functions in non-tangentially accessible domains
• Crossing estimates and convergence of Dirichlet functions along random walk and diffusion paths
• Harmonic functions on planar and almost planar graphs and manifolds, via circle packings
• Hyperbolic and parabolic packings
• Martin boundary of a fractal domain
• Minimal Positive Harmonic Functions
• Oded Schramm: from circle packing to SLE
• On the equivalence of parabolic Harnack inequalities and heat kernel estimates
• Principle de Harnack à la frontière et théorème de Fatou pour un opérateur elliptique dans un domaine lipschitzien
• Probability on trees and networks
• Probability. Theory and examples.
• Random Walks on Infinite Graphs and Groups
• Robust discrete complex analysis: a toolbox
• Scale-invariant boundary Harnack principle in inner uniform domains
• Symmetric Markov processes, time change, and boundary theory
• The Poincaré inequality for vector fields satisfying Hörmander's condition
• The boundary of a square tiling of a graph coincides with the Poisson boundary
• The convergence of circle packings to the Riemann mapping
• Volume growth and stochastic completeness of graphs

Cited in

(20)

• Optimal enclosing regions in planar graphs
• Random walk on random planar maps: spectral dimension, resistance and displacement
• The Tutte embedding of the mated-CRT map converges to Liouville quantum gravity
• Harmonic functions on mated-CRT maps
• The boundary of a square tiling of a graph coincides with the Poisson boundary
• Anomalous diffusion of random walk on random planar maps
• Robust discrete complex analysis: a toolbox
• Harmonic Dirichlet functions on planar graphs
• Martin boundary for the similarity walk in a planar triangle
• Quasisymmetric uniformization and heat kernel estimates
• The Dirichlet problem for orthodiagonal maps
• Uniform spanning forests of planar graphs
• Circle boundaries of planar graphs
• Unimodular hyperbolic triangulations: circle packing and random walk
• On the boundary at infinity for branching random walk
• Conformal growth rates and spectral geometry on distributional limits of graphs
• Anchored expansion, speed and the Poisson-Voronoi tessellation in symmetric spaces
• Indistinguishability of collections of trees in the uniform spanning forest
• Boundaries of planar graphs: a unified approach
• scientific article; zbMATH DE number 6903525 (Why is no real title available?)

Describes a project that uses

Uses Software

• CirclePack

This page was built for publication: Boundaries of planar graphs, via circle packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726798)