Boundaries of planar graphs, via circle packings

DOI10.1214/15-AOP1014zbMATH Open1339.05061arXiv1311.3363MaRDI QIDQ726798FDOQ726798

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)

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).

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

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

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)

Cites Work

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

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
• Quasisymmetric uniformization and heat kernel estimates
• Martin boundary for the similarity walk in a planar triangle
• Harmonic Dirichlet functions on planar graphs
• 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
• Title not available (Why is that?)

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)