TY - JOUR

T1 - Strong Isoperimetric Inequalities and Combinatorial Curvatures on Multiply Connected Planar Graphs

AU - Oh, Byung Geun

AU - Seo, Jeehyeon

PY - 2016/10/1

Y1 - 2016/10/1

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

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

KW - Combinatorial curvature

KW - Multiply connected planar graph

KW - Strong isoperimetric inequality

UR - http://www.scopus.com/inward/record.url?scp=84979986000&partnerID=8YFLogxK

U2 - 10.1007/s00454-016-9805-3

DO - 10.1007/s00454-016-9805-3

M3 - Article

AN - SCOPUS:84979986000

VL - 56

SP - 558

EP - 591

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 3

ER -