On flat submaps of maps of non-positive curvature

arXiv:1702.08205v1 [] 27 Feb 2017

A.Yu. Olshanskii, M.V. Sapir∗

Abstract
We prove that for every r > 0 if a non-positively curved (p, q)-map M contains no flat
submaps of radius r, then the area of M does not exceed Crn for some constant C. This
strengthens a theorem of Ivanov and Schupp. We show that an infinite (p, q)-map which
tessellates the plane is quasi-isometric to the Euclidean plane if and only if the map contains
only finitely many non-flat vertices and faces. We also generalize Ivanov and Schupp’s result
to a much larger class of maps, namely to maps with angle functions.

Contents
1 Introduction

1

2 Large flat submaps of (p, q)-maps
2.1 A lemma about curvatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Weakly exterior faces and the interior of a (p, q)-map. . . . . . . . . . . . . .
2.3 Adjustment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Connecting non-flat vertices and faces with the boundary . . . . . . . . . . .
2.5 Cutting the map along its connecting subgraph and the proof of Theorem 2.8

.
.
.
.
.

6
6
8
13
13
14

3 (p, q)-maps that are quasi-isometric to R2
3.1 The “if” part of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 The “only if” part of Theorem 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . .

16
16
19

4 Maps with angle functions

23

1

.
.
.
.
.

Introduction

Recall that a map is a finite, connected and simply-connected 2-complex embedded in the
Euclidean plane. So its 1-skeleton is a finite, connected plane graph. The cells of dimensions
0, 1 and 2 are called vertices, edges and faces, respectively. Every edge e has an orientation; so
it starts at the vertex e− and ends at e+ , and (e−1 )− = e+ , (e−1 )+ = e− for the inverse edge
e−1 , which has the same support as e. The degree d(o) of a vertex o is the number of oriented
edges e with e− = o. In particular, every loop e (an edge which connects a vertex o with itself)
together with e−1 contributes 2 to the degree of o.
If a closed path q = e1 . . . ek is the boundary of a face Π, then the degree d(Π) of Π is the
length |q| = k. In particular, if both e and e−1 occur in the boundary path of a face, they
∗

Both authors were supported in part by the NSF grant DMS 1418506.The first author is also supported by
RFFI grant 15-01-05823

1

contribute 2 to the degree of that face. Similarly one defines the perimeter |∂M | of a map M as
the length of a closed boundary path of M .
A submap N of a map M is the subcomplex bounded by a closed curve which can be made
simple by an arbitrary small transformation. So either N is a map or it can be turned into a
map after such small transformation.
In group theory, maps appear most often as van Kampen diagrams. Many algebraic and
geometric results about groups (say, the small cancelation theory, and construction of various
groups with “extreme properties” such as Tarski monsters [7, 8]) are obtained by establishing
combinatorial properties of corresponding maps and their submaps. A typical example of such
a statement: The area (i.e., the number of faces) of every reduced van Kampen diagram over
a finite group presentation is at most linear in terms of its perimeter if and only if the group
is hyperbolic. In other words, hyperbolic groups are precisely the finitely presented groups
with linear Dehn functions. One of recurrent features of van Kampen diagrams is existence of
“special” submaps in every van Kampen diagram of large area. For example, in the proof of
the upper bound of the Dehn function of a group constructed in [10] using an S-machine, it is
proved that if the area of a reduced diagram is large enough, then up to a homotopy which does
not change the area very much, the area is “concentrated” is a few special subdiagrams called
“discs” (these are the subdiagrams simulating the work of the S-machine).
A remarkable result of this kind was proved by Ivanov and Schupp in [6]. Recall that an
edge e of a map M is called exterior if it belongs to a boundary path of M . A face Π of M is
called exterior if its boundary ∂Π has a common edge with ∂(M ). An exterior vertex is one of
the vertices of the boundary path. Non-exterior faces, vertices and edges are called interior.
A map M is called a (p, q)-map if every interior face Π in M has degree at least p and the
degree of every interior vertex is at least q. Note that if a group presentation P = hX Ri satisfies
the small cancelation condition C(p) − T (q), then every reduced van Kampen diagram over P
is a (p, q)-map if we ignore all interior vertices of degree 2 (as in [7, 6]). It is well known (see
[7]) that if 1p + 1q is smaller than 12 (i.e., the curvature of the presentation is negative), then the
group is hyperbolic and its Dehn function is linear. The case when p1 + 1q > 21 is not interesting.
Indeed, by a result of Gol’berg [4, 8], every group can be given by a presentation satisfying C(5)
and T (3) and by a presentation satisfying C(3) and T (5) and hence by a presentation satisfying
C(p) and T (q) for every p ≥ 3, q ≥ 3 with 1p + 1q > 12 (see [4, 8]). If p1 + 1q = 12 (i.e., the
“curvature” is non-positive), and so (p, q) is either (3, 6), (4, 4) or (6, 3)), then the group has at
most quadratic Dehn function [7, Theorem V.6.2].
A submap of a (p, q)-map is called flat if each of its faces is flat, i.e. has degree p, and each
interior vertex is flat, i.e. has degree q. The radius of a map is the maximal distance from a
vertex to the boundary of the map.
Ivanov and Schupp [6] proved that if a (p, q)-map M , p1 + 1q = 12 , has no flat submaps of radius
r (they call flat submaps regular ), then the area of the map is linear in terms of its perimeter
with the multiplicative constant depending on r. More precisely, Ivanov and Schupp proved the
following
Theorem 1.1 (Ivanov, Schupp, [6]). Let M be a finite (p, q)-map with perimeter n such that
the maximal distance from a vertex in M to a boundary vertex or to a non-flat vertex or face is
r. Then the area of M does not exceed L(r)n, where L(r) is some exponential function in r.
Theorem 1.1 implies that if a group presentation P = hX Ri satisfies conditions C(p) and
T (q), p1 + 1q = 12 , and the radius of every flat van Kampen diagram over P does not exceed
certain constant, then the Dehn function of the group given by P is linear, hence the group is
hyperbolic. Using this, Ivanov and Schupp proved hyperbolicity of many 1-related groups.
2

In this paper, we strengthen Theorem 1.1 in two ways. First, we replace the exponential
upper bound for L(r) by a linear upper bound. Second, we extend Theorem 1.1 to a much larger
class of maps called “maps with angle functions”.
Let us call a submap of a (p, q)-map simple if it is bounded by a simple closed curve. Note that
the closure of the union of faces from a non-simple submap may not be simply connected (Figure
1) while the closure of the union of faces from a simple submap is always simply connected.
A

G

B

F

E

J

C

D
I

H

Figure 1: The thick path ABCDEF BAGHIJA is simple up to an arbitrary small deformation.
It bounds a non-simple submap.
Let p = 4, 3 or 6. Let S p be the usual tessellation of the plane by p-gons. Then for every
n ≥ 0 the standard map Snp is constructed as follows. By definition S0p is a vertex o in T . If
p
the submap Snp of T is constructed, then Sn+1
is the (closure of the) union of all faces having a
p
p
common vertex with Sn . Then Sn is a simple (p, q)-map. For example, then Sn4 is the 2n × 2nsquare tessellated by unit squares, Sn3 is a regular hexagon with side length n tessellated by
equilateral triangles with side length 1, Sn6 can be viewed as the weak dual1 to the (3, 6)-map
3 , only starting with a triangle face instead of a vertex.
constructed just as Sn+1
Remark 1.2. Every simple (p, q)-map, 1p + 1q = 21 , of radius r, contains a simple submap M ′
which is isomorphic to Snp for n = O(r). The submap M ′ can be obtained in a similar manner
as Snp . Pick a vertex o in M at distance r from the boundary of M . This is the submap M0 . If
Mi is already constructed, then Mi+1 is obtained from Mi by adding all faces having a vertex
in common with Mi . The process continues until one of the vertices in Mi is exterior. In that
case we set M ′ = Mi . Of course it should be explained why Mi+1 is indeed a simple standard
submap provided Mi is already a simple standard submap. It is not as obvious as it seems. The
explanation uses Lemma 2.2 below, it is given in Remark 2.4.
Our main result is the following
Theorem 1.3 (See Theorem 2.1 below). If a (p, q)-map M does not contain flat simple submaps
of radius ≥ r, then the area of M is at most crn for some constant c.
1
Recall that if M is a map, then the weak dual map M̄ is obtained by putting a vertex in every (bounded)
face, and for every edge shared by two faces of M , connect the two vertices from these faces by an edge crossing
that edge. Thus the vertices of M̄ correspond to faces of M , edges of M̄ correspond to interior edges of M , faces
of M̄ correspond to interior vertices of M .

3

Note that the statement of Theorem 2.1 is non-trivial even for the van Kampen diagrams
over the standard presentation of Z2 although there is a significantly easier proof in this case.
Theorem 2.1 is applicable to van Kampen diagrams over any C(p) − T (q)-presentations with
1
1
1
p + q = 2 , say, the standard presentations of 2-dimensional Right Angled Artin groups or the
fundamental groups of alternating knots.
Theorem 2.1 is proved in Section 2. The plan of the proof is the following. First for every
map M and every two (real) numbers p, q with 1p + 1q = 12 we define curvature of faces and
vertices of M as numbers proportional to the excessive degrees, and show that the sum of all
curvatures is equal to p. Then we assume that p, q are positive integers (so (p, q) is (3, 6), (4, 4)
or (6, 3)) and note that by a simple transformation of the map, we can assume that all faces
of M have degrees between p and 2p − 1, the perimeter of the map after this transformation
increases by a factor of ≤ p − 1 and the set of (simple) flat submaps does not change. The
key “contraction” Lemma 2.6 says that the perimeter of the interior M 0 which is the union of
all faces of M having no boundary vertices of M , is “substantially smaller” than the perimeter
of M . From this, we deduce, first, that the area of M is O(Rn), where R is the radius of M .
Second, we deduce that one can cut M along paths of linear in n total length so that in the
resulting map M̃ all non-flat vertices and faces are on the boundary. Then the radius R̃ of M̃
is less than r + p. Hence Area(M ) = Area(M̃ ) = O(R̃ñ) = O(rn).
In Section 3 we consider infinite maps on the plane, i.e. tessellations of R2 . An infinite map
is called proper if its support, i.e. the union of all faces, edges and vertices is the whole plane
R2 and every disc in R2 intersects only a finite number of faces, edges and vertices of the map.
Our main result is the following:
Theorem 1.4 (See Theorem 3.1). Let M be a proper (p, q)-map with p1 + 1q = 12 . Then the
1-skeleton of M with its path metric is quasi-isometric to the Euclidean plane if an only if M
has only finitely many non-flat vertices and faces.
Our proof of Theorem 1.4 proceeds as follows. Suppose that a proper map M has finite
number non-flat vertices and faces. Then we modify it in a finite sequence of steps. At each
step we reduce the number of non-flat faces and vertices while keeping the map quasi-isometric
to M . As a result we get a proper map M ′ with at most one non-flat vertex and no non-flat
faces. Such a map is naturally subdivided by infinite paths emanating from the non-flat vertex
into a finite number of convex infinite submaps, each of which is quasi-isometric to a quadrant
of the Euclidean plane. Combining the corresponding quasi-isometries, we get a quasi-isometry
between M ′ and R2 . The main tool in the proof is the notion of infinite corridor, that is an
infinite sequence of faces in M where each consecutive faces share an edge. This gives the “if”
part of the theorem.
For the “only if” part, we prove that if a proper map M has infinitely many non-flat vertices
or faces, then for every constant c it contains an infinite c-separated set S of vertices which
has super-quadratic growth function (that is the function that for every n gives the number of
vertices from S at distance ≤ n from a given vertex is super-quadratic). This cannot happen if M
was quasi-isometric to R2 . The key tool in proving this part of the theorem is the “contraction”
Lemma 2.6 from the proof of Theorem 2.1. We construct a sequence of submaps N (r) such that
the boundaries of N (r) contain large c-separated sets of vertices. In order to prove this property
of N (r) we use winding numbers of piece-wise geodesic paths in M passing through vertices of
∂(N (r)) around a vertex which is deep inside N (r).
Bruce Kleiner and Michah Sageev explained to us that the “only if” part of Theorem 1.4
can be deduced from Theorem 4.1 of their paper [1] (joint with Mladen Bestvina). If we view
every face of a proper (p, q)-map M as a regular Euclidean n-gone, then the map M turns
4

into a CAT(0) 2-complex M ′ which is quasi-isometric to the original map. Then Part 1 of [1,
Theorem 4.1] implies that M has a locally finite second homology class whose support S is
locally isometric to the Euclidean plane outside some finite ball. It remains to notice that the
only such homology class is (up to a scalar multiple) the fundamental class of M . Hence M
is locally flat outside a finite ball. Bruce Kleiner also explained how to deduce the “if” part
of Theorem 1.4 using Riemannian geometry. First we “smooth out” the CAT(0) 2-complex
M which is locally flat outside a finite ball to obtain (using the Cartan-Hadamard theorem) a
2-dimensional Riemannian manifold M ′ with the same property and which is quasi-isometric to
the map M . Then we use the Rauch comparison theorem to establish a bi-Lipschitz equivalence
between M ′ and the Euclidean plane.
Note that our proof of Theorem 1.4 is completely self-contained, short and uses only basic
graph theory.
In Section 4 we consider the class of maps with angle functions. Let o be a vertex on the
boundary of a face Π of a map M . A corner of Π at o is the pair of two consecutive oriented
edges e and f of ∂(Π) with e+ = f− = o. (f −1 and e−1 define the same corner.) An angle
function assigns a non-negative number (angle) to each corner of each cell. Then the curvature
of an interior vertex o is 2π minus the sum of all angles at o. The curvature of an exterior vertex
is defined in a similar way. The curvature of a face of perimeter d is the sum of angles of corners
of this face minus the sum of angles of an Euclinean d-gone (that is π(d − 2)). A map with an
angle function is called flat if all its faces and interior vertices are of curvature 0. A map with
an angle function is called a (δ, b)-map, δ > 0, b > 0 if the curvature of every non-flat vertex and
face does not exceed −δ and the degree of every vertex and face does not exceed b.
The class of (δ, b)-maps is very large. By Fáry’s theorem (see [11, 2]), every finite planar
graph M without double edges and loops can be drawn on the Euclidean plane using only
straight line segments for edges. The proof from [2] shows that if M is a plane map, then one
can assume that the graph with straight edges is isomorphic to M as a 2-complex. For a map
with straight edges, we can assign to each corner its Euclidean angle, making the map flat.
Note that many authors considered van Kampen diagrams as maps with angle functions.
Some of the earliest implementations of this idea are in the papers [3] by Steve Gersten, [9] by
Steve Pride and [5] by Jim Howie.
It is easy to see that a (finitely presented) group G has a (finite) presentation P = hX | Ri
such that every van Kampen diagram over P can be assigned an angle function which makes
the diagram a flat map if and only if one can find a finite generating set of the group which
does not contain involutions. Such a finite generating set exists if and only if the group is not
an extension of an Abelian group A by the automorphism of order 2 which takes every element
of A to its inverse.
We will show in Remark 4.4 that every (p, q)-map can be transferred into a (δ, b)-map with
angle function without decreasing the area, or increasing the perimeter or the set of flat vertices
and faces. Thus the following theorem is a generalization of Ivanov and Schupp’s Theorem 1.1
to a much wider class of maps.
Theorem 1.5. Suppose that M is a (δ, b)-map of perimeter n and the distance of every vertex of
M to a boundary vertex or to a non-flat vertex or face of M is at most r. Then Area(M ) ≤ Ln,
where L is exponential in r.
The key part of the (very short) proof of Theorem 1.5 (see Section 4) is Lemma 4.2 which
shows that in every non-positively curved map with an angle function, the sum of curvatures of
all faces and interior vertices exceeds π(2 − n) where n is the perimeter of the map.

5

2

Large flat submaps of (p, q)-maps

Although every edge has an orientation, when counting the numbers of edges (or faces) in a map,
we take usually any pair (e, e−1 ) as one non-oriented edge (e.g., E is the number of non-oriented
edges, when we apply Euler’s formula). The boundary path p of a map or a face is considered
up to cyclic permutations and taking inverse paths p−1 .
The number of faces in M is called the area of M , denoted Area(M ).
Here is a precise formulation of our main result.
Theorem 2.1. Let p, q be positive integers with 1p + 1q = 12 , C = 23 (p − 1)(q + 1). Then the area
of M does not exceed C(r + p)n, provided M contains no simple flat submaps of radius greater
than r.

2.1

A lemma about curvatures

Given a pair (p, q) of arbitrary (possibly negative) real numbers with p1 + 1q = 21 , the curvature
of a face Π in a map M is defined as curvp,q (Π) = p − d(Π). Let o be a vertex in M . Then
let µ(o) be the number of times the boundary path x goes through the vertex o. For example,
the multiplicity µ(o) is 1 if the closed path x passes through o only once, and µ(o) = 0 if o is
an interior vertex. The curvature curvp,q (o) of a vertex o is defined as pq (q − d(o)) − µ(o). Let
Iv = Iv (M ) be the sum of curvatures of all vertices of M , and let If = If (M ) be the sum of
curvatures of all faces of M .
The following lemma follows from Theorem 3.1 from [7, Capter V], we include the proof for
completeness and because it is significantly easier than in [7].
Lemma 2.2. For an arbitrary map M and arbitrary real p, q with p1 + 1q = 21 , we have Iv +If = p.
Proof. The statement is obvious for a map consisting of one vertex. So assume that M has
more than one vertex, hence it has no vertices of degree 0. Let us assign weight 1 to every
non-oriented edge of the map M . Then the sum of all weights is the number E of edges in M .
Now let us make each edge give 1q of its weight to each of its vertices (if it has only one vertex,
the edge gives it 2q ) and p1 to each of the (at most two) faces containing that edge. Thus the
P
sum of weights of all vertices of M is equal to o 1q d(o), where o runs over all vertices of M .
P
The sum of weights of all faces is Π p1 d(Π), where the sum runs over all faces of M .
By the assumption 1p + 1q = 12 , every edge separating two faces becomes completely weightless
(it gives 1p to each of the faces and 1q to each of its vertices). For the same reason, an edge e
of the boundary path x = ∂(M ) becomes of weight p1 if it lies on the boundary of a face, or 2p
otherwise. In the later case, the non-oriented edge e occurs in the path x twice (with different
orientations). Therefore after the redistribution of weights, the sum of weighs of all edges in M
is equal to 1p n where n is the perimeter of the map.
Thus, the total weight is equal to
X1
X1
1
d(o) +
d(Π) + n.
E=
q
p
p
o
Π

Since E − V − F = −1 by Euler’s formula, where V and F are numbers of vertices and faces in
M respectively, we have:
−1 =

X1
o

q

d(o) +

X
1
d(Π) + n − V − F =
p
p
o

X1
Π

6



 X

1
1
1
d(o) − 1 +
d(Π) − 1 + n. (2.1)
q
p
p
Π

P
Notice also that n = v µ(o) where v runs over all vertices of M (indeed, µ(o) = 0 for all
interior vertices and µ(o) is the number of times the boundary path passes through o). Therefore
we can rewrite (2.1) as follows:
 X

X 1
1
1
−1 =
d(o) − 1 + µ(o) +
d(Π) − 1 .
q
p
p
o
Π

Since the first of these sums is − p1 Iv and the second sum is − p1 If , we deduce that Iv + If = p.

Remark 2.3. A result similar to Lemma 2.2 is true for maps on arbitrary surfaces S with
boundary. It is easy to see that in that case the right hand side is equal to pχ(S) where χ(S) is
the Euler characteristic of the smallest subsurface of S containing the map.
Remark 2.4. Let us use Lemma 2.2 to complete the proof from Remark 1.2 about standard
submaps of simple flat maps. Here we consider the case p = q = 4 only, leaving the other two
cases to the reader as an exercise. Let, as in Remark 1.2, M be a simple flat map of radius r.
We set M0 to be a vertex o at distance r from the boundary of M , and assume that for i ≥ 0,
the submap Mi is constructed and this submap is simple and isomorphic to the standard map
Si4 which is the n × n-square (where n = 2i) tessellated by unit squares. Counting the difference
between the degrees of the vertices from ∂Mi in M and in Mi , we obtain exactly 4n + 4 oriented
edges e1 , ..., e4n+4 with (ej )− ∈ ∂(Mi ) and (ej )+ 6∈ Mi . We claim that no two of the edges ej , ek ,
j 6= k, are mutually inverse and no two of the vertices (ej )+ , (ek )+ coincide.
Indeed, suppose that ej = e−1
k . Then this edge and a subpath of ∂Mi bound a submap N
having no faces from Mi . All exterior vertices of N , except for (ej )± , have degree at least 3 in

N

Mi

Figure 2: The case when ei = e−1
k .
N because the degrees of these vertices in Mi are at most 3 while there degrees in M are 4.
Therefore the (4, 4)-curvature of every face and vertex in the flat map N , except for (ej )± , are
non-positive, while the curvature of each of (ej )± is at most 1. Hence the sum If + Iv of all
these curvatures for N is at most 2 < 4, which contradicts Lemma 2.2.
7

In case when (ej )+ = (ek )+ , we consider the submap N , without faces from Mi , bounded by
ej , e−1
k and by a subpath of ∂Mi . It has at most 3 vertices of positive curvature (equal to 1),
namely, (ej )− , (ej )+ = (ek )+ and (ek )− . This again contradicts Lemma 2.2 since 3 < 4.
Now if we assume that edges e1 , ..., e4n+4 are enumerated clockwise, we see that for each j,
ej , ej+1 , j = 1, ..., 4n + 4 (where j + 1 is 1 if j = 4n + 4) must belong to the same face Πj which
shares a vertex with ∂(Mi ) and every face sharing a vertex with ∂(Mi ) is one of the Πj . Each
pair of consecutive faces Πj , Πj+1 share exactly one edge ej+1 . Hence Mi+1 is isomorphic to
the (n + 2) × (n + 2)-square tessellated by unit squares. The boundary of Mi+1 is simple since
otherwise a part of this boundary bounds a flat submap N with at most one exterior vertex of
positive curvature contrary to Lemma 2.2 for N since 1 < 4.

2.2

Weakly exterior faces and the interior of a (p, q)-map.

In this section, p and q are postive integers satisfying 1p + 1q = 12 .
A face (edge) in a map M is called strongly interior if it does not share a vertex with ∂(M ),
otherwise it is called weakly exterior.
Lemma 2.5. Let M be a (p, q)-map, o1 , ..., om be its exterior
Pvertices (counted counterclockwise).
Then the number of weakly exterior faces does not exceed
d(oi ) − 2m.

Proof. Induction on the number of faces in M . If M has a cut vertex, then M is a union of two
submaps M1 and M2 intersecting by a vertex, and it is easy to see that the statement for M
follows from the statements for M1 and M2 . Thus we can assume that the boundary path of
M is simple. Then every exterior vertex oj belongs to d(oj ) − 1 weakly
P exterior faces,
P and two
vertices oj , oj+1 (addition modulo m) belong to one face. So the sum (d(oj )−1) =
d(oj )−m
overcounts weakly exterior faces by at least m. The statement of the lemma then follows.
By the interior M 0 of M we mean the union of all strongly interior faces of M , their vertices
and edges. Note that M 0 may be empty. It may also be not connected in which case, it coincides
with the union of its maximal simple submaps M10 , M20 , ... It follows that every edge of ∂Mi0
belongs to a face of Mi0 and to a weakly exterior face of M .
Hence the intersection of different submaps is either empty or consists of one vertex. Let us
call these submaps the components of M 0 . Thus the boundary paths y01 , y02 , . . . of the components
0
M10 , M
2 , ... are simple (see Fig. 1). Below we denote by y the union of these boundaries and set
P
|y| = i |y0i |.
In the next lemma, we induct on the type of a map M . By definition, the type τ = τ (Π)
of a face Π in M is the number of interior (non-oriented) edges in ∂Π. If m = Area(M ) and
(τ1 , τ2 , ..., τm ) is the m-tuple of the types of all the faces of M with τ1 ≥ τ2 ≥ ..., then τ (M ) is
the infinite string (τ1 , . . . , τm , −1, −1, . . . ). We order types lexicographically: τ (M ) ≥ τ (M ′ ) =
(τ1′ , τ2′ , . . . ) if τ1 > τ1′ or τ1 = τ1′ but τ2 > τ2′ , and so on. For example, a map with only one face
has the type (0, −1, −1, . . . ). The set of types is obviously well ordered.
Lemma 2.6. Assume that a (p, q) map M has at least one face. Also assume that the degree of
every face of M is at least p. Let x be the boundary path of M and y is defined as above. Then
|x| − |y| ≥ −If − 2Ivi + p

(2.2)

where If is the sum of the (p, q)-curvatures of all faces and Ivi is the sum of (p, q)-curvatures of
all interior vertices of M .

8

M

M10

M20

Figure 3: The interior of a map and its components

Proof. Let us denote −If − 2Ivi by J = J(M ). Thus we need to prove that |x| − |y| ≥ J + p.
Step 1. The statement of the lemma is true if M has only one face Π, because we have
|x| = d(Π) ≥ p, |y| = 0, If = p − d(Π) and Ivi = 0. Since the smallest type of a (p, q) map that
has faces is the type (0, −1, −1, ...) of a map consisting of one face (recall that we assume that
(p, q)-maps do not have vertices of degree 1), this gives the base of induction and we can assume
that
(U1 ) The area of M is greater than 1.
Step 2. Suppose that M can be cut into two maps M1 and M2 with smaller number of
faces by a path of length at most 1. Defining parameters x(j), y(j), If (j), Ivi (j) of the map Mj ,
j = 1, 2, in the natural way (x(j) is the boundary path of Mj , etc.), we have:
• |x(1)| + |x(2)| ≤ |x| + 2,
• |y| = |y(1)| + |y(2)|,
• If = If (1) + If (2) and Ivi = Ivi (1) + Ivi (2) since no interior vertex of M became exterior
after the cutting.
Since p ≥ 2, the statement of the lemma follows from inequalities |x(j)| − |y(j)| ≥ −If (j) −
2Ivi (j) + p (where j = 1, 2), which hold, since τ (Mj ) < τ (M ) because Area(Mj ) < Area(M ).
Thus, we may assume further that
(U2 ) M has no cutting paths of length ≤ 1, hence, in particular, the boundary path
x is simple.

9

Step 3. Assume there is an exterior vertex o of degree d > 3. Let e1 , e2 , ..., ed be all edges
ending in o, so that e1 and e2 are on the boundary path of a face Π1 , e2 and e3 are on the
boundary path of a face Π2 , etc. Suppose (e1 )− = o′ . Then let us split the edge e2 into two
edges by a new vertex o′′ in the middle of e2 , and replace e1 with a new edge e′1 going from
o′ to o′′ . Note that this transformation does not change the type of M . Indeed, since e1 is an
exterior edge, the only faces that are changed by this transformation are Π1 , Π2 , but the number
of interior edges on ∂(Πj ), j = 1, 2, does not change (one of the two edges which are parts of the
exterior edge e2 is exterior in the new map and one is interior, and the new edge e′1 is exterior
as was e1 ), hence τ (Πj ), j = 1, 2, does not change, and the type of the map does not change as
well. Also this transformation does not change the set of interior vertices of the map and their
degrees. The degree of Π2 increases by 1 (because of the new vertex o′ ). Thus both −If and |x|
increases by 1 and Ivi does not change. Hence the value of |x| − J does not change. The degree
of the vertex o decreases by 1 and the degree of the new vertex o′ is 3. Therefore by doing this
transformation, we will eventually get a map with the degrees of all exterior vertices at most 3
with the same path y and the difference |x| − J as for M .
e1

✱
Π1 e2 ✱
✱
✱ Π
2
✱

e′1

ed

ot

.
.

⇒

.

ot
✱
′
Π1 ot✱
✱
✱ Π
2
✱

ed
.
.
.

Figure 4: Step 3.
So we continue the proof under the additional assumption
(U3 ) The degree of every exterior vertex is at most 3.
Remark 2.7. Note that (U3 ) implies that every weakly exterior face of M is exterior, i.e., every
face which shares a vertex with ∂(M ) also shares an edge with ∂(M ).
Step 4. Assume there is a vertex o of degree 2 on an exterior face Π. Let us join two edges
incident with o into one edge and remove the vertex o. This does not change τ (M ) because
only exterior edges and vertices are affected. Then the boundary y of the interior of the map
does not change, the contribution of Π to J decreases by 1, contributions of all other faces and
vertices remain the same, and |x| also decreases by 1, hence |x| − |y| − J will not change. Hence
(U4 ) We can remove vertices of degree 2 of x (joining pairs of edges that share these
vertices), provided the property d(Π) ≥ p is preserved, and we can split edges of x
by new vertices of degree 2 without changing |x| − |y| − J.
Step 5. Suppose an exterior face Π of M has boundary path of the form uw, where u is a
maximal subpath of the boundary path ∂Π contained as a subpath in the boundary path x of
M . Note that |w| ≥ 2, because we excluded cutting paths of length ≤ 1 by (U2 ) and M has
more than one face by (U1 ). Also note that |u| > 0 by Remark 2.7.
Suppose that w has an exterior vertex o which is not equal to the end vertices of w. Then we
add a vertex o′ of degree 2 on u (using (U4 ) ) and connect o and o′ by a new edge g cutting up
10

Π into two faces of degrees d1 and d2 , where d1 + d2 − 3 = d = d(Π). For the new map M ′ (with
parameters x′ , y′ , etc.) we have |x′ | = |x| + 1, y′ = y. Instead of the face Π of curvature p − d,
we have two faces with curvatures p − d1 and p − d2 . Hence If − If′ = 3 − p. Since the degrees
of interior vertices were preserved, we have J ′ − J = 3 − p and (|x′ | − J ′ ) − (|x| − J) = p − 2.
According to (U4 ), the same difference p − 2 has a map with additional vertices of degree 2 on
u. So we may assume that d1 , d2 ≥ p.
Cutting along g, we obtain new maps M1 and M2 with τ (Mj ) < τ (M ) (j = 1, 2), since Π is
subdivided into two faces with τ (Πj ) < τ (Π), j = 1, 2, where τ (Πj ) is computed in Mj . For the
parameters xj , yj , Jj , etc. of the maps Mj , j = 1, 2, we have |x1 | + |x2 | = |x| + 3, |y1 | + |y2 | = |y|
and J1 + J2 = J ′ = J + 3 − p. So, by induction on the type, we obtain
|x| − |y| − J − p = (|x1 | − |y1 | − J1 − p) + (|x2 | − |y2 | − J2 − p) − 3 + 3 ≥ 0 + 0 − 3 + 3 = 0,
as desired. Thus, we may assume that
(U5 ) For every exterior face Π as above, the path w has no exterior vertices except
its end vertices.
u

or′

Π
w

⇒

Π1

o

u

g Π2
o

Figure 5: Step 5.
Step 6. Properties (U1 )-(U5 ) imply the following property
(U6 ) For every weakly exterior face Π of M , we have ∂(Π) = euf v where u = u(Π) is
the subpath of the boundary path of M , |u(Π)| > 0, and e, f are edges with exactly
one exterior vertex while v = v(Π) has no exterior vertices.
Using the notation of Property (U6 ), suppose now that |v(Π)| > 1, i.e., v(Π) = v′ v′′ with
|v′ |, |v′′ | > 0. Let o be the last vertex of v′ . Then we add a new vertex o′ of degree 2 on an edge
of u (subdividing that edge into two edges) and add a new edge t connecting o and o′ . As a
result, the face Π of degree d = d(Π) is subdivided into two faces: a face Π′ of degree d′ and a
face Π′′ of degree d′′ , where d′ + d′′ = d + 3. Let M ′ be the new map with parameters x′ , y′ , If′ , J ′ ,
etc. We have τ (M ′ ) < τ (M ) since τ (Π′ ), τ (Π′′ ) < τ (Π) by (U6 ).
By (U4 ), we can add new vertices of degree 2 to ∂(Π′ ), ∂(Π′′ ) so we can assume that d′ =
d(Π′ ) ≥ p, d′′ = d(Π′′ ) ≥ p. The contributions of Π′ and Π′′ to If′ are p−d′ and p−d′′ , respectively,
while the contribution of Π to If was p−d. So If −If′ = p−(d′ +d′′ −3)+(d′ −p)+(d′′ −p) = 3−p.
The contribution of the interior vertex o to 2Ivi is greater than its contribution to 2(Ivi )′ by 2p
q

since this vertex is incident to the new edge t, i.e., 2(Ivi )′ −2Ivi = 2p/q. Thus J −J ′ = p−3− 2p
q =
1
1
1
′
−1 because p + q = 2 . However we also have |x| − |x | = −1 since one edge is subdivided by the
vertex o′ , and so |x′ | − J ′ = x − J. Thus we can assume,
(U ) M satisfies (U6 ) and for every exterior face Π, |v(Π)| ≤ 1.
11

os′

u
e

f

Π
v ′′

o

⇒

e

Π′′
v ′′

v′

t
o

Π′

f

v′

Figure 6: Step 6.

Step 7. Now we consider the cases p = 3, 4, 6 separately. Since |v(Π)| ≤ 1 by (U ), we have
|u(Π)| ≥ p − 3, and by (U4 ), one may assume that every exterior face has degree p if p > 3 and
has degree 4 if p = 3.
Since every exterior vertex has degree 2 or 3 (by (U3 )), the difference |x| − |y| is not smaller
than the sum S of |u(Π)| − |v(Π)| for all exterior faces Π.
Case p = 4, q = 4. In this case the degree of every exterior face is 4. Then a vertex of
degree 2 can occur only on the path u(Π) for some exterior face Π with |v(Π)| = 0. Let N be
the number of vertices of degree 2 on ∂(M ). Then the contribution of the face containing that
vertex to the sum S is 2 and S ≥ 2N . The contribution of faces Π with |u(Π)| = |v(Π)| = 1 is
0. The sum Ivb of curvatures of exterior vertices is




4
4
(4 − 2) − 1 N +
(4 − 3) − 1 (|x| − N ) = N.
4
4
By Lemma 2.2, Ivi +Ivb +If = 4. Thus N +Ivi +Ic = 4, hence 2N +2(Ivi +If ) = 8, and 2N ≥ J +8
because J = −2Ivi − If and If ≤ 0 by the assumption of the lemma. Therefore
|x| − |y| ≥ J + 8 ≥ J + p.
Case p = 6, q = 3. Now every exterior face of M has degree 6. Let Ni , be the number of
weakly exterior faces Π with |v(Π)| = i, i = 0, 1. Then |u(Π)| is 4 or 3, respectively, and so
|x| ≥ 4N0 + 3N1 and |y| ≤ N1 . So |x| − |y| ≥ 4N0 + 2N1 .
Every exterior face has either 3 or 2 vertices of degree 2. It is easy to compute now that the
sum Ivb of curvatures of the vertices of x is




6
6
(3N0 + 2N1 )
(3 − 2) − 1 + (|x|− 3N0 − 2N1 )
(3 − 3) − 1 = −|x|+ 6N0 + 4N1 = 2N0 + N1 .
3
3
Since by Lemma 2.2, Ivb + Ivi + If = 6, we have 2N0 + N1 + Ivi + If = 6. Hence J + p < 12 + J ≤
2(−Ivi − If + 6) = 4N0 + 2N1 ≤ |x| − |y|, as required.
Case p = 3, q = 6. Let N1 be the number of exterior faces Π of degree 4 with |u(Π)| = 2,
|v(Π)| = 0, and N0 be the number of exterior faces Π of degree 4 with |u(Π)| = |v(Π)| = 1.
Then we have |x| ≥ 2N1 + N0 , |y| ≤ N0 , and Ivb = N1 + 12 (|x| − N1 ) = 12 (|x| + N1 ), because the
curvature of an exterior vertex of degree 2 (respectively, 3) is 12 (8 − 2) − 1 = 1 (respectively, 21 ).
Since Ivb + Ivi + If = 3 by Lemma 2.2, we get |x| = 2Ivb − N1 = 2(−Ivi − If + 3) − N1 . Note that
−If ≥ N0 + N1 since each quadrangle contributes −1 to the sum If . Hence
|x| = 2(−Ivi − If + 3) − N1 = J − If + 6 − N1 ≥ J + N0 + N1 + 6 − N1 = J + N0 + 6
Therefore |x| − |y| ≥ J + N0 + 6 − N0 ≥ J + 6 > J + p, as desired.
12

2.3

Adjustment

Note that it is enough to prove Theorem 2.1 for simple maps. Let M be a simple (p, q)-map,
1
1
1
p + q = 2 . Every face of M of degree ≥ 2p can be subdivided by diagonals into faces of degrees
p + 1, ..., 2p − 1. Every vertex o of degree d ≥ 2q can be replaced by two (nearby) vertices o′ , o′′
connected by an edge such that d(o′ ) + d(o′′ ) = d(o) + 2 and d(o′ ) = q + 1. It can be done so
that if o is an exterior vertex, then exactly one of the vertices o′ , o′′ is exterior in the resulting
map. Each such transformation increases the total number of vertices and faces of negative
(p, q)-curvature but it does not increase the number and the curvatures of the vertices and faces
having non-negative curvature. Since the sum If + Iv of (p, q)-curvatures of all vertices and
faces cannot exceed p by Lemma 2.2, any sequence of subdivisions of vertices and faces as above
terminates. Clearly, if M is a (p, q)-map, then the new map M ′ is again a (p, q)-map, it has
non-smaller area than M , the same perimeter, and the set of (simple) flat submaps in M ′ is a
subset of the set of (simple) flat submaps of M because the subdivisions do not introduce new
flat vertices or faces. The map M ′ satisfies the following condition.
(B) The degree of every face (every vertex) of the simple (p, q)-map M ′ is less than 2p (resp.
2q).
If we have a (p, q)-map M with condition (B), then one can construct a new map M ′
satisfying condition (B), where all faces (not just interior ones) have degrees at least p. Namely,
one subsequently cuts out the exterior faces of degree less than p (and also the edges containing
the vertices of degree 1 if such edges appear). The perimeter of M ′ is at most (p − 1)n, where n
is the perimeter of M , Area(M ′ ) ≥ Area(M ) − n, and the maps M and M ′ have the same flat
submaps.
The map M ′ is a (p, q)-map satisfying the following additional condition
(D) The degree of every face of M ′ is ≥ p.
Let us call a (p, q)-map with the additional assumptions (B) and (D) a {p, q}-map. It is
easy to see that Theorem 2.1 follows from
Theorem 2.8. The area of an arbitrary simple {p, q}-map M does not exceed ( 3q
2 + 1)(r + p)n,
provided M contains no simple flat submaps of radius greater than r.
Indeed, let M ′ be the {p, q}-map obtaining from a (p, q)-map M satisfying the assumption
of Theorem 2.1 and condition (B) after removing some exterior faces. By Theorem 2.8, we
3q
have Area(M ′ ) ≤ ( 3q
2 + 1)(r + p)(p − 1)n. Hence Area(M ) ≤ ( 2 + 1)(r + p)(p − 1)n + n ≤
3
2 (q + 1)(r + p)(p − 1)n.

2.4

Connecting non-flat vertices and faces with the boundary

Note that all non-flat faces and all interior non-flat vertices of a {p,q}-map M have negative
curvatures.
If M contains non-flat faces or vertices, there exists a subgraph Γ of the 1-skeleton of M ,
such that every non-flat face or vertex of M can be connected with ∂M by a path in Γ We
will assume that Γ is chosen with minimal number of edges D(M ). Then Γ will be called a
connecting subgraph of M .
Remark 2.9. The minimality of Γ implies that every vertex of Γ can be connected in Γ with
∂M by a unique reduced path. It follows that Γ is a forest, where every maximal subtree has
exactly one vertex on the boundary ∂M .
13

We shall use the notation from Section 2.2. Thus x is the boundary path of M , y is the union
of the boundary paths of components of M 0 , etc.
Lemma 2.10. We have D(M ) ≤ (p − 1)|x|.
Proof. We shall induct on the area m of M . The statement is true if m = 1 since in this case
D(M ) = 0.
Let D0 = D(M 0 ) and let Γ0 be the corresponding connecting subgraph of the interior M 0 .
By the induction hypothesis, D0 ≤ (p − 1)|y|.
Let A0 (resp., A) be the number of non-flat faces and interior vertices in M 0 (in M ). By
Remark 2.9, Γ0 has at most A0 vertices on ∂M 0 , and so one needs at most A0 paths z1 , z2 , . . . ,
to connect them with ∂M . Besides there are A − A0 non-flat faces and interior vertices in M
which are not counted in A0 . One can connect them with ∂M adding at most A − A0 connecting
paths y1 , y2 , . . . to obtain a graph Γ′ connecting all non-flat faces and interior vertices of M with
∂(M ). The lengths |zi | and |yj | cannot exceed a half of the maximum of the perimeters of faces,
and so |zi |, |yj | ≤ p − 1 by Property (B). Therefore D(M ) ≤ D0 + A(p − 1).
Since every non-flat face (resp. non-flat interior vertex) has curvature at most −1 (respectively, at most − 21 ), we have A ≤ −If − 2Ivi = J ≤ |x| − |y| − p by Lemma 2.6. Therefore
D(M ) ≤ D0 + J(p − 1) ≤ (p − 1)|y| + J(p − 1) ≤ (p − 1)(|y| + (|x| − |y| − p)) < (p − 1)|x|

2.5

Cutting the map along its connecting subgraph and the proof of Theorem
2.8

As before p, q are positive integers with

1
p

+

1
q

= 12 .

Lemma 2.11. Let M be a {p, q}-map of radius 0 (i.e., all vertices of M are exterior) and
perimeter n > 0. Then Area(M ) ≤ q(n−2)
2p .
Proof. Induction on the number of faces in M . The statement is easy to check if M contains
only one face. If M contains more than one face, then M has a cut vertex or cut edge. In each
of the two cases, the cut vertex or the cut edge separates M into two submaps M1 and M2 with
perimeters n1 , n2 such that n1 + n2 ≤ n + 2. Therefore
Area(M ) = Area(M1 ) + Area(M2 ) ≤

q(n − 2)
q(n1 − 2) q(n2 − 2)
+
≤
.
2p
2p
2p

Lemma 2.12. Let M be a {p, q}-map. Then the sum Ivb of curvatures of exterior vertices
satisfies Ivb ≥ p.
Proof. Indeed, we have Ivb + Ivi + If = p by Lemma 2.2. Since Ivi ≤ 0 and If ≤ 0, we have
Ivb ≥ p.
Lemma 2.13. Let M be a {p, q}-map with perimeter n > 0. Then the number N of weakly
exterior faces of M is at most pq n − q.

14

Proof. Let o1 , ..., om (m ≤ n) be the exterior vertices of M . Then
X p
pX
Ivb =
( (q − d(oj )) − µ(oj )) = −
d(oj ) + pm − n
q
q
j

since

P

j

µ(oj ) = n. Therefore we have

X
q
q b
−Iv + pm − n ≤ −q + qm − n
d(oj ) =
p
p
j

by Lemma 2.12. By Lemma 2.5, the number N of weakly exterior faces in M is at most
P
j d(oj ) − 2m Therefore


q
q
q
N ≤ −q + (q − 2)m − n ≤ −q + q − 2 −
n= n−q
p
p
p
since

1
p

+

1
q

= 12 .

Lemma 2.14. If the radius of a {p, q}-map M is at most r − 1 and perimeter is n, then the
area of M does not exceed qp rn.
Proof. If r = 1 then this follows from Lemma 2.11, so let r > 1. Let M 0 be the interior
of M . Its boundary y is the union of the boundaries of the components M10 , M20 , . . . having
radii ≤ r − 2. So one may assume by induction on r that Area(M 0 ) < qp (r − 1)|y|, which
does not exceed qp (r − 1)(n − p) by Lemma 2.6. It follows from Lemma 2.13 that Area(M ) <
q
q
q
p (r − 1)(n − p) + p n − q < p rn.
Proof of Theorem 2.8. Let Γ be a connecting graph of M . Let e be an non-oriented
edge of Γ with one vertex on ∂M . Then cutting M along e, one obtains a {p, q}-map M1 with
perimeter |x| + 2, where all non-flat faces and vertices are connected with ∂M1 by paths in the
graph Γ1 , where Γ1 is obtained from Γ by removing the edge e. We can continue cutting this
way along the edges of Γ, until we obtain a {p, q}-map M̄ of perimeter |x| + 2D(M ) ≤ (2p − 1)|x|
(by Lemma 2.10), where every vertex and every face of curvature > 0 is (weakly) exterior. Thus
every component of the interior M̄ 0 of M̄ is a simple flat map.

Γ

⇒

✥✥

❇❇
❵❵

M̄

M
Figure 7: Cutting the map M along the edges of Γ.

If M̄ 0 is empty, then the radius r̄ of M̄ is at most r − 1 since by (B), the degree of every
exterior face in M̄ is less than 2p. Hence by Lemma 2.14 for M̄ , we have
Area(M ) = Area(M̄ ) ≤

3q
q
r(2p − 1)n ≤ ( + 1)(r + p)n
p
2
15

1
1
1
since pq (2p − 1) = 3q
2 + 1 by equality p + q = 2 , and the theorem is proved.
If M̄ 0 is not empty, then again by (B), it has a component N of radius r̄ 0 ≥ r̄ − p + 1
The map N is a simple flat submap of M . Hence its radius r̄ 0 does not exceed r. Therefore
r̄ − p + 1 ≤ r and r̄ ≤ r + p − 1. By Lemma 2.14,

Area(M ) = Area(M̄ ) ≤

3

3q
q
(2p − 1)(r + p − 1 + 1)n = ( + 1)(r + p)n
p
2

(p, q)-maps that are quasi-isometric to R2

Recall that a metric space X with distance function distX is (L, K)-quasi-isometric to a metric
space Y with distance function distY , where L > 1, K > 0, if there exists a mapping φ from
X to Y such that Y coincides with a tubular neighborhood of φ(X) and for every two vertices
o1 , o2 of X we have
−K +

1
distX (o1 , o2 ) < distY (φ(o1 ), φ(o2 )) < K + LdistX (o1 , o2 ).
L

Two metric spaces X and Y are quasi-isometric if there is an (L, K)-quasi-isometry X → Y for
some L and K. This relation is reflexive, symmetric and transitive.
In this section we consider infinite planar maps. Here such a map M is called proper if the
support of M is the whole plane R2 , and every disc on R2 intersects finitely many faces, edges
and vertices of M . The metric on M is the combinatorial path metric on its 1-skeleton.
Theorem 3.1. Let M be a proper (p, q)-map, where positive integers p and q satisfy 1p + 1q = 12 .
Then the 1-skeleton of M is quasi-isometric to Euclidean plane if and only if M has finite
number of non-flat vertices and faces.
We will provide a proof for the case p = q = 4, the other two cases are left for the reader
(see Remark 3.10).

3.1

The “if” part of Theorem 3.1

A corridor B of M is a finite sequence of faces, where any two consecutive faces share a gluing
boundary edge, and two gluing edges of a face are not adjacent in the boundary path of the
face. In detail: a corridor is a sequence
(e0 , Π1 , e1 , Π2 , . . . , et−1 , Πt , et ),
where ei−1 and e−1
are non-adjacent edges in the boundary of the face Πi for i = 1, . . . , t.
i
❛❛
❛

e0

Π1

e1

q
Π2

e2

e3

...
...

et−1 Π
t

et

q′
Figure 8: A corridor
′ −1
′
The boundary of B has the form e0 qe−1
t (q ) , where the sides q and q consist of non-gluing
edges of the faces Π1 , . . . , Πt .

16

Lemma 3.2. In the above notation, no vertex of a (4, 4)-map is passed by a side q or by q′
twice.
Proof. Assume that a corridor B is a counter-example. Then we may assume that q is a simple
closed path bounding a submap N of minimal possible area. So N contains no faces from B.
Every vertex of q, except for the initial (= terminal) vertex o has degree at least 4 in M , and
so its degree in N is at least 3, as it follows from the definition of a corridor: two gluing edges
of a face in a corridor are not adjacent in the boundary path of the face. Thus, the only vertex
that can give a negative contribution to the sum If + Iv from Lemma 2.2 for the map N is o.
But this contribution is at most 1, and so we have If + Iv ≤ 1, contrary to Lemma 2.2.

▲▲

q
N

B

Figure 9: A corridor touching itself
Lemma 3.2 allows us to extend an arbitrary corridor infinitely in both directions:
(. . . , e−1 , Π0 , e0 , Π1 , e1 , Π2 , . . . , et−1 , Πt , et , Πt+1 . . . ),
its sides are infinite simple paths subdividing the plane in two parts (because the map M is
proper), these are infinite corridors. One can also consider semi-infinite corridors of the form
(e0 , Π1 , e1 , Π2 , . . . , et−1 , Πt , et , . . . ).
Lemma 3.3. Let M be the map from Theorem 3.1 with a finite set of non-flat faces and vertices.
Then the 1-skeleton of M is quasi-isometric to the 1-skeleton of a map with finitely many non-flat
vertices and without non-flat faces.
Proof. Consider a infinite corridor B = (. . . , e0 , Π1 , e1 , Π2 , . . . , et−1 , Πt , et , . . . ) containing a nonflat face Πt . Since the number of non-flat faces in M is finite, we can assume that all the faces
Πt+1 , . . . are flat.
Let p, p′ be the two sides of B so that each ei connects a vertex oi on p with a vertex o′i on
′
p.
Since d = d(Πt ) ≥ 5, without loss of generality we can assume that the subpath w of p
connecting ot−1 and ot has length at least 2, so it can be decomposed as w = vu, where u is one
edge connecting o′′ with ot and |v| > 0. Then we modify the faces in B as follows: replace the
17

u

v
...
et−1
...

Πt

u

v
et

et+1

...
... ⇒

...
et−1
...

Πt

ft ft+1

...
...

B
Figure 10: Modifying non-flat faces in a corridor

gluing edge et by a new gluing edge ft connecting o′′ and o′t , and replace every gluing edge es
with s > t by the new gluing edge fs connecting os−1 with o′s (see Figure 10). Then the degree
of Π decreases by 1 and the degrees of all other faces are preserved. To complete the proof by
induction, it suffices to notice that the 1-skeleton of new map M ′ is quasi-isometric to 1-skeleton
of M , since the distances between the vertices cannot increase/decrease more than two times
when we passing from M to M ′ .
Lemma 3.4. Let B = (. . . , e0 , Π1 , e1 , Π2 , . . . , et−1 , Πt , et , . . . ) be a infinite corridor in M , where
every face Πi has degree 4, and so Π has the boundary of the form ei−1 fi (ei )−1 gi , where fi and
gi are edges. Excising the faces of B from M and identifying the edges fi and gi (for every
−∞ < i < ∞), one obtains a new map M ′ . We claim that M ′ is a (4, 4)-map whose 1-skeleton
is quasi-isometric to the 1-skeleton of M .
Proof. Every end vertex of ei has degree ≥ 4 in M . So the same must be true in M ′ . Hence M ′
is a (4, 4)-map.

B

fi
ei−1
gi

ei

⇒

fi = gi

Figure 11: Collapsing gluing edges of a corridor
If two vertices can be connected in M ′ by a path p of length m, then their preimages in M
can be connected in M by a path q of length at most 2m + 1 since q can be constructed from the
edges of p and the gluing edges of B. Conversely, the distance between two vertices in M ′ does
not exceeds the distance between them in M . The quasi-isometry of the 1-skeletons follows.
Proof of the ”if part” of Theorem 3.1. Suppose that M has finitely many non-flat vertices and
faces. By lemma 3.3, we may assume that M has no non-flat faces, and so every face has degree
4. Let two distinct non-flat vertices o and o′ be connected by a shortest path p. Then we chose
an edge e on p and consider a infinite corridor B, where e is one of the gluing edges of B. Then
the transformation M → M ′ from Lemma 3.4 decreases the sum of distances between non-flat
vertices and replaces M by a quasi-isometric map M ′ . So after a number of such transformations,
we shall have a (4, 4)-map without non-flat faces and with at most one non-flat vertex o. We
will use the same notation M for it.
Let us enumerate the edges e1 , . . . , ek with initial vertex o in clockwise order; so o lies on the
boundaries ei fi gi e−1
i+1 (indexes are taken modulo k) of k quadrangles Π1 , . . . , Πk . Consider the
semi-infinite corridors B1 = (e1 , Π1 , g1 , Π′1 . . . ) and C1 = (e2 , Π1 , f1 , . . . ) starting with the face
Π1 . They define semi-infinite sides q1 and q′1 starting at o. Since M is proper, the paths q1 , q2
bound a submap Q1 of the plane.
18

There is a semi-infinite corridor C1′ starting with the second edge of q′1 and the face Π′1 . This
corridor has to share the whole side with C1 since it is made of quadrangles and all the vertices,
except for o, have degree 4. Similarly, the semi-infinite corridor C1′′ starting with the third edge
of q′1 is glued up to C1′ along the whole side, and so on.
Therefore Q1 with its path metric is isometric to a standard quadrant of the square grid Z2 .

q2
✟
✟✟

B1
Q1

e3
e2
Π1
e1
C1′

q1

C1′′

C1

Figure 12: Representing a map as a union of several quadrants of Z2 .
Similarly we have quadrants Q2 , . . . , Qk , where each Qi is bounded by semi-infinite paths qi
and q′i , and as above, we have q′i = qi+1 (indices modulo k). The 1-skeleton of every submap Qi
is quasi-isometric to a quadrant on the Euclidean plane R2 with the Euclidean metric which, in
turn, is quasi-isometric to a part Si of the plane bounded by two rays with common origin and
angle 2π/k so that the union of all Si is the whole plane R2 (use polar coordinates). Combining
all these quasi-isometries and using the fact that a quadrant of R2 is convex, we get a quasiisometry between the 1-skeleton of M and R2 .

3.2

The “only if” part of Theorem 3.1

Let M be a proper (4, 4)-map having infinitely many non-flat vertices and faces. By contradiction, suppose that M with its path metric distM is (L, K)-quasi-isometric (L > 1, K > 0) to R2
If distM (o1 , o2 ) > c for some c ≥ KL, then distR2 (φ(o1 ), φ(o2 )) > c0 = (c − KL)/L and so the
growth of every c-separated set2 S of vertices of M is at most quadratic, that is the function
γS,o (r) = |{o′ ∈ V ′ | distM (o, o′ ) ≤ r}| is at most quadratic in r.
The number of vertices in a submap M ′ of M will be denoted by area(M ′ ) (recall that
Area(M ′ ) denotes the number of faces in M ′ ).
We start with the following well known
Lemma 3.5. (See Theorem 6.2 in [7, Chapter V]. Also it immediately follows from Lemmas
2.13 and 2.6 by induction on n.) If N is a (4, 4)-map with perimeter n, then area(N ) ≤ kn2 for
some constant k > 0.
Now we are going to modify faces of high degree.
2

A set of points S in a metric space X is called c-separated if distX (o1 , o2 ) > c for every two distinct points
o1 , o2 ∈ S.

19

Lemma 3.6. There exists a map M ′ on the plane
1. with the same set V of vertices as M ,
2. with infinite set of non-flat vertices and faces,
3. for a marked vertex o ∈ V and every o′ ∈ V , distM (o, o′ ) = distM ′ (o, o′ ),
4. for arbitrary vertices o′ , o′′ , we have distM ′ (o′ , o′′ ) ≤ distM (o′ , o′′ ),
5. the degrees of all faces are at most 6.
Proof. Let Π be a face with d = d(Π) ≥ 7, and vertices o1 , ..., od in the clockwise order. Consider
the difference f (i) = dist(oi , o) − dist(oi+j , o) (indices modulo d). It is non-negative if oi is the
farthest vertex from o among o1 , ..., od , and it is non-positive if oi is the closest one. Since
|dist(om , o) − dist(om+1 , o)| ≤ 1, we have |f (m) − f (m + 1)| ≤ 2 for any m, and so there is i such
that f (i) = |dist(oi , o) − dist(oi+j , o)| ≤ 1.
Let us connect vertices oi , oi+j by a new, diagonal edge e inside the cell Π, so that Π is
divided into two new cells Π′ , Π′′ both of degrees at least 4 and at least one of degree at least
5. This operation does not introduce any new vertices. Let M ′ be the new map on the plane.
It is clear that Properties 1 and 4 of the lemma hold.
Let us show that distance from every vertex o′ to o in M ′ is the same as in M (Property
3). Let g be a geodesic in M ′ connecting o′ and o. If g does not contain the new edge e, then
the distance between o′ and o did not change. So suppose that g contains e. Without loss of
generality we can assume that the vertices of g in the natural order are o′ , ..., oi , oi+j , ..., o. Since
g is a geodesic, e appears in g only once, and distM ′ (oi+j , o) = distM (oi+j , o), and distM ′ (oi , o) =
distM (oi+j , o) + 1. By the choice of the pair (oi , oi+j ), f (i) ∈ {0, 1, −1}. Since distM (oi , o) ≥
distM ′ (oi , o) we can deduce that distM (oi , o) = distM ′ (oi , o), so there exists a geodesic g ′ in M ′
connecting o′ and o and avoiding e. Hence distM ′ (o′ , o) = distM (o′ , o).
This implies that we can cut all faces of degree ≥ 7 by diagonals into several parts so that
the resulting map on R2 satisfies all five properties of the lemma.
Lemma 3.6 implies that for the map M ′ the growth function γS,o of every c-separated set
S of vertices with respect to vertex o is at most quadratic if c is large enough (because every
c-separated set S of vertices in M ′ is c-separated in M by Property 4, and the functions γS,o (r)
for M and M ′ are the same by Property 3). To obtain a contradiction with this quadratic
growth, Lemma 3.6 allows us to assume from now on that the degrees of all faces in M are at
most 6.
Lemma 3.7. For every r > 0 there exists a simple submap N = N (r) of M containing the
vertex o, such that distM (o, ∂(N )) ≥ r and the maximal distance (in M ) from o to an exterior
vertex of N is at most r + 2.
Proof. Let N be the smallest (with respect to the length of the boundary) submap of M containing all faces Π of M with distM (o, Π) ≤ r − 1. Such submap N exists since M is locally
finite. We claim that the boundary path of N has no cut points. Indeed, let o′ be a cut point on
∂(N ) and o′ subdivides N into two submaps N1 , N2 containing faces, N1 ∩ N2 = {o′ }, o ∈ N1 .
Suppose that N2 contains a face Π at distance (in M ) at most r − 1 from o. Let g be a geodesic
connecting o and Π′ in M . Then every vertex on g is at distance (in M ) at most r − 1 from o.
Hence every face of M having a common vertex with g is in N . Thus g is a path in the interior

20

of N . Since g connects a vertex in N1 with a vertex in N2 , g must contain o′ . Hence o′ is an
interior vertex of N , a contradiction.
Since the boundary path ∂N contains no cut points and has minimal length, it is simple.
There are no vertices o′ ∈ ∂(N ) at distance (in M ) at most r − 1 from o. Indeed, otherwise
every face of M containing o′ would be at distance ≤ r − 1 from o, and would be contained in
N , hence o would be an interior vertex in N , a contradiction.
Suppose that N contains an exterior vertex o′ at distance (in M ) at least r + 3 from o. Then
′
o belongs to an exterior face Π of N . Since d(Π) ≤ 6, we have distM (o, Π) ≥ r. Therefore if
we remove Π from M together with the longest subpath of ∂(Π) containing o′ and contained in
∂(N ), we get a smaller submap N ′ of N containing all faces of M at distance ≤ r − 1 from o, a
contradiction. Hence dist(o, o′ ) ≤ r + 2 for every o′ ∈ ∂(M ).
Let Φ(r) be the number of vertices o′ of M with distM (o′ , o) ≤ r.
Lemma 3.8. The function Φ is super-quadratic, i.e limr→∞ Φ(r)/r 2 = ∞.
Proof. Let us denote by φ(r) the minimum of the numbers of vertices on the boundaries of the
finite submaps Q with the property that Q is simple and distM (o, ∂Q) ≥ r. For any Q with this
property, let N be the component of the interior Q0 containing o. Since every (exterior) face of
Q has degree at most 6, the boundary yN of N satisfies inequality |yN | ≥ φ(r − 3). If x is the
boundary path of Q, then by Lemma 2.6, |x| ≥ |yN | + J + 4, where J = −If (Q) − 2Ivi (Q). Since
J is not less that the number K = K(Q) of non-flat faces in Q plus the number of interior in Q
non-flat vertices, we have |x| > |yN | + K ≥ φ(r − 3) + K, and so φ(r) > φ(r − 3) + K.
If a non-flat face Π (or vertex o′ ) lies in M at a distance ≤ r − 1 from o, then it belongs
to Q (resp., it is interior in Q). Indeed, if Π is not in Q or o′ is not an interior vertex of Q,
then any path connecting Π or o′ with o has to insersect ∂Q, which contradicts the property
distM (o, ∂Q) ≥ r. Hence K ≥ φ(r − 1), where ψ(r − 1) is the number of non-flat vertices and
faces of M at the distance ≤ r − 1 from o. Therefore
P φ(r) > φ(r − 3) + ψ(r − 1).
Since ψ(r) → ∞ as r → ∞, we have φ(r)/r ≥ 1r 0≤i≤r/6 ψ(r−1−3i) ≥ ψ(⌊r/2⌋−1)/6 → ∞.
Since the boundaries of the maps N (r) and N (r ′ ) from Lemma 3.7 do not intersect if |r−r ′ | ≥
3, we have
1
1 X
φ(r − 2 − 3i) ≥ φ([r/2] − 2) → ∞
Φ(r)/r 2 ≥ 2
r
6r
0≤i≤r/6

Lemma 3.9. For an arbitrary integer c ≥ 1, there is a super-linear function α(r) = αc (r)
such that the boundary of every submap N (r) satisfying the condition of Lemma 3.7 contains a
c-separated set of vertices S with |S| ≥ α(r).
Proof. We may assume that r > c. The simple boundary path x of N (r) has winding number
±1 around the vertex o, and it is a sequence of edges, i.e., of subpaths of length 1 ≤ c. Therefore
there is the smallest t ≥ 1 and the vertices o1 , . . . , ot of x such that distM (oi , oi+1 ) ≤ c (indices
modulo t) and the geodesic paths zi = oi − oi+1 (in M ) form a product z = z1 . . . zt with non-zero
winding number around o. (Self-intersections are allowed for z, but no zi goes through o since
|zi | ≤ c < r ≤ distM (o, oi ), and so the winding number is well defined.)
Suppose there is a pair of distinct vertices oi , oj , where i < j and i − j 6= ±1 (mod t),
with dist(oi , oj ) ≤ c. Then a geodesic path z̄ = oi − oj defines two new closed paths z′ =
−1
z̄zj . . . zt z1 . . . zi−1 and z′′ = z−1
i . . . zj−1 z̄ with numbers of factors less than t. Since one of the

21

paths z′ and z′′ has nonzero winding number with respect to o, this contradicts the minimality in
the choice of t. Hence dist(o
p i , oj ) > c, and so one can chose the set S of cardinality ≥ (t − 1)/2.
Assume now that t < 4 r 2 Φ(r − C/2), where Φ(r) is defined before Lemma 3.8. Note that o
belongs to a submap L bounded by a simple closed path w, which is a product of some
p pieces of
the paths zi -s. Therefore |w| ≤ |z| ≤ tc, and by Lemma 3.5, area(L) ≤ k(ct)2 ≤ Dr Φ(r − c/2),
where D = kc2 .
On the other hand, distM (o′ , o) ≥ r − c/2 for every vertex o′ of w since zi ≤ c for everyp
i. Therefore area(L) ≥ Φ(r − c/2) by Lemma 3.8. We obtain inequality Φ(r − c/2) ≤
Dr Φ(r − c/2), which can hold only for finitely p
many values of r since the function Φ is
super-quadratic by Lemma 3.8. Thus t = t(r) ≥ 4pr 2 Φ(r − c/2) for every r ≥ r0 , and since
|S| ≥ 12 (t − 1), one can define α(r) to be equal to 21 ( 4 r 2 Φ(r − c/2) − 1) if r ≥ r0 and α(r) = 1
if r < r0 .
Now we can prove that for any given integer c ≥ 1, the map M contains an infinite c-separated
set S of vertices which grows super-quadratically with respect to the vertex o, which would give
the desired contradiction. The boundary ∂N (r) has a c-separated subset Sr with at least α(r)
vertices. Since the distance between ∂N (r) and ∂N (r ′ ) is greater than c for r − r ′ ≥ c + 3, the
union S(r) = Sr ∪ Sr−(c+3) ∪ Sr−2(c+3) ∪ . . . is c-separated and
|S(r)|/r 2 ≥

1
r2

X

α(r − i(c + 3)) ≤

r
0≤i≤ 2(c+3)

1
2(c + 3)r

min

r
0≤i≤ 2(c+3)

α(r − i(c + 3)) → ∞

as r → ∞ since r − i(c + 3) ≥ r/2 and the function α is super-linear by Lemma 3.9.
Remark 3.10. The proof of Theorem 3.1 for (4, 4)-maps can be easily adapted for (6, 3)- and
(3, 6)-maps. The “only if” part does not need virtually any modification.
To prove the ”if” part for (3, 6)-maps by contradiction, again one can use Lemma 3.6 to
uniformly bound the degrees of all faces. Then one can subdivide non-flat faces by diagonals
and obtain a quasi-isometric (3, 6) map M ′ , where all the faces have degree 3. If two distinct
triangles of M ′ share an edge e, we say that they form a diamond with the hidden edge e. We
can view diamonds as new faces, and build analogs of corridors made of diamonds, where the
gluing edges of a diamond are not adjacent. The additional requirement is that the hidden edges
of neighbor diamonds in a corridor have no common vertices (see Fig. 11). The vertices on sides
q and q′ of a corridor B have degrees at most 4 in B. Then the statement of Lemma 3.2 holds
since every exterior vertex (except for one) of the submap N should have degree ≥ 4. Hence one
obtains the notion of an infinite and semi-infinite corridors. The Lemma 3.4 reduces the task
to a map M with single non-flat vertex, and the rest of the proof of Theorem 3.1 is as above:
the quadrangles ei fi gi ei+1 should be replaced by diamonds and the corridors B, C1 , C1′ , C1′′ ,...
are now built from diamonds. If now one erases the hidden edges of all these diamonds in the
quadrant Q1 , . . . , then the obtained quadrants Q′i -s are (4, 4)-maps quasi-isometric to Qi -s. So
our task is reduces to the case of (4, 4)-maps.

B

Figure 13: Corridor and hidden edges in (3, 6)-maps

22

The case of (6, 3)-map M can be easily reduces to (3, 6). For this goal, one bounds the
degrees of faces as above, then chooses a new vertex inside of every face Π and connects it with
the vertices of ∂Π. The resulting map is a (3, 6)-map which is quasi-isometric to M , it has
finitely many non-flat vertices and faces.

4

Maps with angle functions

Let M be a map with an angle function (for the definition, see Section 1).
For every face Π (vertex o) we denote by ΣΠ (resp. Σo ) the sum of the angles of the corners
of Π (resp. corners at o). Note that if there are no corners at a vertex o, then Σo = 0. We
define the curvature curv(Π) of a face Π with degree d = d(Π) as ΣΠ − π(d − 2)). The curvature
curv(o) of a vertex o is defined as (2 − µ(o))π − Σo , where, as before, µ(o) is the multiplicity of
o in the boundary path of M .
We denote by If (by Iv ) the sum of curvatures of the faces (vertices) of a finite map M . The
following discrete analog of Gauss - Bonnet formula is well known but we include its proof here
anyway.
Lemma 4.1. Let a map M with angle function have at least one edge. Then If + Iv = 2π.
Proof. Let V, E and F be the numbers of vertices, non-oriented edges and faces
P in M and n be
the perimeter of M . It was observed
in
the
proof
of
Lemma
2.2
that
n
=
o µ(o) (the sum
P
over all vertices in M ). Since Π d(Π) (the sum over all faces in M ) is equal to the number
of exterior
Pfaces in MPplus twice the number of the interior edges in M , we have
P edges of the
2E = Π d(Π) + n = Π d(Π) + o µ(o). Hence
!
X
X
X
X
ΣΠ −
Σo
If + Iv =
(2 − d(Π))π +
(2 − µ(o))π +
o

Π

=

X
Π

2π +

X

2π − π

o

X
Π

d(Π) +

Π

X

!

µ(o)

o

o

+ 0 = 2πF + 2πV − 2πE = 2π

In the next lemma, Ivi (resp., Ivb ) is the sum of the curvatures of interior (exterior) vertices
in M .
Lemma 4.2. Let M be a map of perimeter n ≥ 1 with angle function. Assume that the
curvatures of the faces and of the interior vertices of a map M are non-positive. Then nπ ≥
−If − Ivi + 2π.
Proof. On the one hand, it follows from the definition that
X
X
Ivb =
((2 − µ(o))π − Σo ) ≤ 2nπ − nπ −
Σo ≤ nπ
o∈∂M

o∈∂M

On the other hand, Lemma 4.1 gives us Ivb + Ivi + If = 2π. Therefore we have nπ + If + Ivi ≥ 2π,
as required.
Recall that a map M is called (δ, b)-map for some δ > 0 and a natural number b > 0 if
(1) the curvature of every non-flat vertex or face does not exceed −δ and
23

(2) the degree of every face and of every vertex in M is at most b.
We denote by B(d, o) the ball of radius d centered at o in a graph G, i.e., the set of vertices
o′ of G such that dist(o′ , o) ≤ d.
The following lemma is well known and obvious.
Lemma 4.3. The inequality |B(d, o)| ≤ bd + 1 holds for any graph where degrees of all vertices
are at most b (hence for (δ, b)-maps).
Proof of Theorem 1.5. Let V be the set of vertices of M which are either exterior or non-flat or
belong to a non-flat face. From the (δ, b)-condition and Lemma 4.2, one deduces that
|V| ≤ n + δ−1 (−Ivi ) + δ−1 b(−If ) ≤ nπ + δ−1 bnπ = (δ−1 b + 1)nπ

(4.3)

For arbitrary vertex o ∈ V, we consider the ball B(o, r). By the assumption of the theorem,
every vertex o′ of M belongs in one of these balls. Therefore by Lemma 4.3, area(M ) ≤
|V| × (br + 1) ≤ (1 + δ−1 b)nπ(br + 1). Since every vertex belongs to the boundaries of at most b
faces, the inequality Area(M ) ≤ Ln follows, provided L ≥ πb(1 + δ−1 b)(br + 1).
Remark 4.4. Theorem 1.5 generalizes Theorem 1.1. Indeed, it is enough to establish Theorem
1.1 for simple maps. As it was explained in Subsection 2.3, every simple (p, q)-map M can be
modified so that the new (p, q)-map M ′ satisfies Condition (B) from Section 2.3. Condition (B)
implies Condition (2) above with b ≥ 11. Moreover the area of M ′ is not smaller than the area
of M , the perimeter of M ′ is the same as the perimeter of M and the maximal distance from a
vertex to an exterior vertex or non-flat vertex or face in M ′ does not exceed that for M . The
(p, q)-map M ′ can be naturally viewed as a map with angle function which assigns to every
. Again, Condition (B) implies Condition (1) above with
corner of a d-gon face the angle π(d−2)
d
π
. It remains to note that the function L(r) in Theorem 1.5 is exponential as in Theorem
δ > 21
1.1.

References
[1] Mladen Bestvina, Bruce Kleiner, Michah Sageev, Quasiflats in CAT(0) 2-complexes. Algebr.
Geom. Topol. 16 (2016), no. 5, 2663–2676.
[2] István Fáry, On straight-line representation of planar graphs. Acta Sci Math. (Szeged),
11(1948), 229–233.
[3] S. M. Gersten, Branched coverings of 2-complexes and diagrammatic reducibility. Trans.
Amer. Math. Soc. 303 (1987), no. 2, 689–706.
[4] A. I. Gol’berg, The impossibility of strengthening certain results of Greendlinger and Lyndon. Uspekhi Mat. Nauk 33 (1978), no. 6(204), 201–202.
[5] James Howie, The quotient of a free product of groups by a single high-powered relator. I.
Pictures. Fifth and higher powers. Proc. London Math. Soc. (3) 59 (1989), no. 3, 507540.
[6] S. V. Ivanov, P. E. Schupp, On the hyperbolicity of small cancellation groups and one-relator
groups. Trans. Amer. Math. Soc. 350 (1998), no. 5, 1851–1894.
[7] Roger Lyndon and Paul Schupp. Combinatorial group theory. Springer-Verlag, 1977.
24

[8] A. Yu. Ol’shanskii. The geometry of defining relations in groups, Nauka, Moscow, 1989.
[9] Stephen J. Pride, Star-complexes, and the dependence problems for hyperbolic complexes.
Glasgow Math. J. 30 (1988), no. 2, 155–170.
[10] Mark Sapir, Jean-Camille Birget, Eliyahu Rips, Isoperimetric and isodiametric functions
of groups. Ann. of Math. (2) 156 (2002), 2, 345–466.
[11] Klaus Wagner, Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen
Mathematiker-Vereinigung, 46 (1936), 26–32.
Alexander Yu. Ol’shanskii
Department of Mathematics
Vanderbilt University
alexander.olshanskiy@vanderbilt.edu
and
Department of Higher Algebra, MEHMAT
Moscow State University

Mark V. Sapir
Department of Mathematics
Vanderbilt University
m.sapir@vanderbilt.edu

25

