Strong Isoperimetric Inequalities and Combinatorial Curvatures on Multiply Connected Planar Graphs

Byung Geun Oh, Jeehyeon Seo

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The main focus of this paper is on hyperbolic properties of multiply connected planar graphs (planar graphs with multiple ends), and in the course we study some problematic phenomena of planar graphs caused by the existence of multiple (or sometimes infinite) ends. Specifically, in the first part of the paper we examine strong isoperimetric inequalities on a multiply connected planar graph G and its dual graph G, and prove that G satisfies a strong isoperimetric inequality if and only if G has the same property, provided that G is either normal or finitely connected and we choose an appropriate notion for strong isoperimetric inequalities. In the second part we study a planar graph G on which negative curvatures uniformly dominate positive curvatures, and give a criterion that guarantees a strong isoperimetric inequality on G. Our criterion is useful in that it can be applied to a graph containing a long and slim subgraph with nonnegative combinatorial curvatures.

Original languageEnglish
Pages (from-to)558-591
Number of pages34
JournalDiscrete and Computational Geometry
Volume56
Issue number3
DOIs
StatePublished - 2016 Oct 1

Keywords

  • Combinatorial curvature
  • Multiply connected planar graph
  • Strong isoperimetric inequality

Fingerprint Dive into the research topics of 'Strong Isoperimetric Inequalities and Combinatorial Curvatures on Multiply Connected Planar Graphs'. Together they form a unique fingerprint.

Cite this