A DECOMPOSITION ALGORITHM OF SKEW-SYMMETRIC AND
SKEW-SYMMETRIZABLE EXCHANGE MATRICES
By
Weiwen Gu

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Mathematics
2013

ABSTRACT
A DECOMPOSITION ALGORITHM OF SKEW-SYMMETRIC AND
SKEW-SYMMETRIZABLE EXCHANGE MATRICES
By
Weiwen Gu
In Fomin, Thurston and Shapiro’s [1], a general construction is described that associates
a quiver or a skew-symmetrizable matrix with a triangulation of a bordered surface. Cluster
algebra is also constructed from the associated matrices. The goals of our study are:
1. Determine when a graph, diagram or integer matrix is associated to a triangulation of
a surface.
2. Find all possible triangulations associated with a given graph, diagram or integer matrix.
3. Find out when a given matrix is associated with different surfaces
In [1] and [2], it is shown that the mutation type of a cluster algebra can be determined
by examining its associated graph or diagram. A cluster algebra is of finite mutation type
if its associated graph or diagram is obtained by gluing certain graphs under certain rules,
or associated to one of finitely many exceptional diagrams. The former type of graphs and
diagrams are called block-decomposable and s-decomposibable respectively. Our main result
is an algorithm that determines if a graph, diagram or matrix is block-decomposable or sdecomposable, and, hence associated with a triangulation of a surface. As a corollary, we
can determine if a cluster algebra is of fine mutation type. Using the algorithm, we can also
determine if a block-decomposable (or s-decomposable) exchange matrix is associated to a
unique surface.

The algorithm is an improvement of the one in [1]. The algorithm in [1] is polynomial in
size of matrix of power 10. Our algorithm is linear. As a possible application, our algorithm
can be used in G. Musiker’s Sage software package for cluster algebra computation (see [3]).

ACKNOWLEDGMENTS

I’d like to thank my advisor Dr. Michael Shapiro for bringing up this problem and tirelessly
helping me during the whole process of writing this dissertation.

iv

TABLE OF CONTENTS

List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

Chapter 1 Fundamental of Cluster Algebra . . . . . . . . . . . . . . . . . . .
1.1 Cluster Algebra of Geometry Type . . . . . . . . . . . . . . . . . . . . . . .
1.2 Cluster Algebra Associated with triangulation of Surface . . . . . . . . . . .

1
1
3

Chapter 2 Introduction to Block Decomposition and s-decomposition
2.1 Block Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 s-decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Graphs with Non-unique Decomposition and Their Associated Surfaces .

.
.
.
.

.
.
.
.

Chapter 3
3.1
3.2

3.3

3.4

3.5

A Decomposition Algorithm for the Oriented Adjacency Graph
of the Triangulations of a Bordered Surface with Marked Points
Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Nodes of Degree Eight . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Nodes of Degree Seven . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Nodes of Degree Six . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Nodes of Degree Five . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nodes of Degree Four . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Four outward edges or four inward edges. . . . . . . . . . . . . . . . .
3.3.2 Three outward edges and one inward edge, or three inward edges and
one outward edge . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3 Two outward edges and two inward edges . . . . . . . . . . . . . . .
3.3.3.1 n = 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3.2 n = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3.3 n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3.4 n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.3.5 n = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Distinguishing the Neighborhoods When n = 4 . . . . . . . . . . . . . . . . .
3.4.1 Node 1 is Connected to Nodes 2 and 3 . . . . . . . . . . . . . . . . .
3.4.2 Node 1 is Connected to Node 2, But Disconnected from Node 3 . . .
3.4.3 Node 1 is Disconnected from Nodes 2,3 . . . . . . . . . . . . . . . .
Simplification on Nodes of Degree Three . . . . . . . . . . . . . . . . . . . .
3.5.1 All edges have the same direction. . . . . . . . . . . . . . . . . . . . .

7
7
9
11

v

14
14
19
20
20
22
25
26
27
27
32
33
33
35
37
38
46
47
55
59
61
61

3.6

3.5.2 Two outward edges and one inward edge . . . . . . . . . . . . . . . .
3.5.3 Determine the Decomposition . . . . . . . . . . . . . . . . . . . . . .
Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapter 4
4.1
4.2

4.3

The Decomposition Algorithm of Skew-symmetrizable Exchange
Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 n = 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 n = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.4 n = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63
71
78

81
81
87
88
88
90
96
102

Chapter 5
5.1
5.2

Graphs with Non-unique Decomposition and Their Associated
Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Associated Surface to A Decomposition of Diagram . . . . . . . . . . . . . . 104
Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Bibliography . . . . . . . . . . . . . . .

vi

. . . . . . . . . . . . . . . . . . . 126

LIST OF TABLES

Table 3.1

Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Table 3.2

A quiver and its two decompositions . . . . . . . . . . . . . . . . . .

16

Table 3.3

Example of neighorhoods . . . . . . . . . . . . . . . . . . . . . . . .

19

Table 4.1

Blocks of Unfolding . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

Table 4.2

n=4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

Table 4.3

n=3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

Table 4.4

n=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

Table 4.5

m=1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96

Table 4.6

m=2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

97

Table 4.7

m=3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

99

Table 5.1

Graph 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Table 5.2

Graph 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Table 5.3

Graph 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Table 5.4

Graph 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Table 5.5

Graph 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Table 5.6

Graph 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Table 5.7

Graph 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Table 5.8

Graph 7’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

vii

Table 5.9

Graph 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Table 5.10

Graph 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

Table 5.11

Graph 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

Table 5.12

Graph 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Table 5.13

Graph 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

Table 5.14

Graph 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Table 5.15

Graph 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Table 5.16

Graph 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Table 5.17

Graph 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Table 5.18

Graph 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

viii

LIST OF FIGURES

Figure 2.1

Triangulation Gluing . . . . . . . . . . . . . . . . . . . . . . . . . .

12

Figure 2.2

Boundary Gluing . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

Figure 2.3

A block-decomposable graph with non-unique surface . . . . . . . .

13

Figure 3.1

Generating a Multi-edge . . . . . . . . . . . . . . . . . . . . . . . .

15

Figure 3.2

Annihilating two edges . . . . . . . . . . . . . . . . . . . . . . . . .

15

Figure 3.3

Node of degree 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Figure 3.4

Node of Degree 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Figure 3.5

Simpliying neighborhoods of nodes with degree 7 . . . . . . . . . . .

23

Figure 3.6

(Deg 6) Node from triangle and square . . . . . . . . . . . . . . . .

23

Figure 3.7

(Deg 6) Replacement . . . . . . . . . . . . . . . . . . . . . . . . . .

23

Figure 3.8

(Deg 6) Disjoint Connected components . . . . . . . . . . . . . . . .

24

Figure 3.9

(Deg 6) Two diamonds glued at one node . . . . . . . . . . . . . . .

24

Figure 3.10

(Deg 6) Two diamonds glued at two nodes . . . . . . . . . . . . . .

24

Figure 3.11

(Deg 6) Simplication for “two diamonds” . . . . . . . . . . . . . . .

25

Figure 3.12

(Deg 5) Spike and square . . . . . . . . . . . . . . . . . . . . . . . .

26

Figure 3.13

(Deg 5) Fork and diamond . . . . . . . . . . . . . . . . . . . . . . .

26

Figure 3.14

(Deg 5) Triangle and diamond . . . . . . . . . . . . . . . . . . . . .

26

Figure 3.15

(Deg 5) Simplification of “fork and diamond” . . . . . . . . . . . . .

27

ix

Figure 3.16

(Deg 5) Simplification of “triangle and diamond” . . . . . . . . . . .

27

Figure 3.17

“Two forks” and its simplification . . . . . . . . . . . . . . . . . . .

27

Figure 3.18

(Deg 4) Fork and triangle . . . . . . . . . . . . . . . . . . . . . . . .

29

Figure 3.19

(Deg 4) Diamond and Spike . . . . . . . . . . . . . . . . . . . . . .

29

Figure 3.20

(Deg 4) Fork + Diamond + Spike . . . . . . . . . . . . . . . . . . .

29

Figure 3.21

Diamond and Spike (Labeled) . . . . . . . . . . . . . . . . . . . . .

30

Figure 3.22

Decomposition of diamond + spike . . . . . . . . . . . . . . . . . . .

30

Figure 3.23

Replacement of diamond + spike . . . . . . . . . . . . . . . . . . . .

30

Figure 3.24

Diamond and spike with y and w connected . . . . . . . . . . . . . .

31

Figure 3.25

(deg 4) n=0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Figure 3.26

(deg 4) n=1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Figure 3.27

(Deg 4) (n=1) Decomposition illustration . . . . . . . . . . . . . . .

34

Figure 3.28

(Deg 4) n=2 first case . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Figure 3.29

(Deg 4) n=2 second case . . . . . . . . . . . . . . . . . . . . . . . .

36

Figure 3.30

Case 2 replacement . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Figure 3.31

(Deg 4) n=3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

Figure 3.32

(Deg 4) Another diamond and spike . . . . . . . . . . . . . . . . . .

38

Figure 3.33

G′ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Figure 3.34

n=4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

Figure 3.35

Two Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

Figure 3.36

Simplification of Two triangles . . . . . . . . . . . . . . . . . . . . .

40

x

Figure 3.37

Two diamonds with mid-edges glued . . . . . . . . . . . . . . . . . .

40

Figure 3.38

Diamond and spike labeled . . . . . . . . . . . . . . . . . . . . . . .

41

Figure 3.39

Another diamond and spike labeled . . . . . . . . . . . . . . . . . .

41

Figure 3.40

Diamond and spike relabeled . . . . . . . . . . . . . . . . . . . . . .

41

Figure 3.41

Decomposition of diamond + spike . . . . . . . . . . . . . . . . . . .

42

Figure 3.42

Illustration of an impossible decomposition . . . . . . . . . . . . . .

42

Figure 3.43

Illustration of a decomposition of diamond + spike . . . . . . . . . .

44

Figure 3.44

Diamond and two spikes . . . . . . . . . . . . . . . . . . . . . . . .

44

Figure 3.45

G’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Figure 3.46

Diamond with two mid-edges . . . . . . . . . . . . . . . . . . . . . .

46

Figure 3.47

Node 1 connected to both 2 and 3 . . . . . . . . . . . . . . . . . . .

47

Figure 3.48

Three triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

Figure 3.49

node 4 connected to 2 and 3 . . . . . . . . . . . . . . . . . . . . . .

51

Figure 3.50

x connected to all four nodes . . . . . . . . . . . . . . . . . . . . . .

53

Figure 3.51

Color matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

Figure 3.52

Color matters, again . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

Figure 3.53

Two diamond with mid-edges glued . . . . . . . . . . . . . . . . . .

60

Figure 3.54

Decomposition of glued diamonds . . . . . . . . . . . . . . . . . . .

60

Figure 3.55

Three edges going outwards . . . . . . . . . . . . . . . . . . . . . . .

62

Figure 3.56

Decomposition of three outgoing edges

. . . . . . . . . . . . . . . .

62

Figure 3.57

Two outgoing and one incoming . . . . . . . . . . . . . . . . . . . .

62

xi

Figure 3.58

Two outgoing and one incoming labeled . . . . . . . . . . . . . . . .

64

Figure 3.59

Diamonds as neighborhood of a node with deg 3 . . . . . . . . . . .

64

Figure 3.60

Triangle and diamond glued by an edge . . . . . . . . . . . . . . . .

64

Figure 3.61

Replacement of 3.60 . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

Figure 3.62

Edge d not annihilated . . . . . . . . . . . . . . . . . . . . . . . . .

65

Figure 3.63

Edge d annihilated by a spike . . . . . . . . . . . . . . . . . . . . . .

65

Figure 3.64

Replacement of 3.63 . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

Figure 3.65

Edge d annihilated by a triangle . . . . . . . . . . . . . . . . . . . .

66

Figure 3.66

Diamond as DCC . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

Figure 3.67

Two tailed Square . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

Figure 3.68

Replacement of 3.67 . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

Figure 3.69

Tailed triangle and diamond . . . . . . . . . . . . . . . . . . . . . .

67

Figure 3.70

Two tailed triangle . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

Figure 3.71

DCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

Figure 3.72

Three tailed Triangle . . . . . . . . . . . . . . . . . . . . . . . . . .

68

Figure 3.73

Three cases. (n=2) . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

Figure 3.74

Two cases. (n=1) . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

Figure 3.75

All decomposable cases for degree 3 . . . . . . . . . . . . . . . . . .

70

Figure 3.76

All Decomposiable case when n=0 . . . . . . . . . . . . . . . . . . .

72

Figure 3.77

x connected to all three nodes . . . . . . . . . . . . . . . . . . . . .

73

Figure 3.78

n=1 and deg of node 1 is three . . . . . . . . . . . . . . . . . . . . .

74

xii

Figure 3.79

Neighborhoods that Have Non-unique Decomposition . . . . . . . .

76

Figure 3.80

An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

Figure 3.81

Step 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

Figure 3.82

Step 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

Figure 3.83

Associated Surface . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

Figure 4.1

Edge of Weight 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

Figure 4.2

Composite Flip . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

Figure 4.3

Diagrams with non-unique s-decompositions . . . . . . . . . . . . . 103

Figure 5.1

Triangulation of surfaces . . . . . . . . . . . . . . . . . . . . . . . . 105

Figure 5.2

˜
A(2, 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

xiii

Chapter 1
Fundamental of Cluster Algebra
In this chapter, we introduce fundamentals of cluster algebra of geometry type that will be
used in later chapters.

1.1

Cluster Algebra of Geometry Type

Definition 1.1. Let B be an integer n × n matrix:
• B is skew-symmetric if bij = −bji for any i, j ∈ [1, n].
• B is skew-symmetrizable if there exists an integer diagonal matrix D, such that DB is
skew-symmetric.
A coefficient group P is a free multiplicative abelian group with finite many generator
g1 , . . . , gm . An ambient group is the field F of rational functions in n independent variables
with coefficients in the field of fractions of the integer group ZP.
˜
Definition 1.2. A seed of geometry type in F is a pair Σ = (x, B), where x = (x1 , . . . , xn )
˜
is a transcendence basis of F over the field of fractions of ZP and B is an n × (n + m) integer
matrix whose principle part B (the matrix formed by first n columns) is sign-skew-symmetric.
˜
We call x in a seed (x, B) a cluster, and its elements (x1 , . . . , xn ), cluster variables.
˜
Denote xn+i = gi for i ∈ [1, m], then x = (x1 , . . . , xn+m ) is called an extended cluster, and
1

˜
xn+1 , . . . , xn+m are stable variables. B is called the exchange matrix and B the extended
exchange matrix.
˜
Definition 1.3. Given a seed Σ = (x, B), the adjacent cluster in direction k ∈ [1, n] is
defined by:
xk = (x \ {xk }) ∪ {x′ }
k
where x′ is defined by the exchange relation:
k
−b
xi ki ;

xi ki +
1≤i≤n+m
bki >0

(1.1)

−b
xi ki ,

b

xk x′ =
k

(1.2)

1≤i≤n+m
bki <0

Equation 1.1 can be rewritten in the form:

b

xi ki + p−
k

xk x′ = p +
k
k
1≤i≤n
bki >0

1≤i≤n
bki <0

where p± ∈ P are given by:
k

−b

b

kn+i
xn+i , p− =
k

p+ =
k
1≤i≤m
bkn+i >0

kn+i
xn+i

(1.3)

1≤i≤m
bkn+i <0

Definition 1.4. Let A = (aij ) and A′ = (a′ ) be two matrices of the same size. We say
ij
that A′ is obtained from A by a matrix mutation in direction k and write A′ = µk (A) if

a′ =
ij




−a ,
 ij

if i = k or j = k



a + |aik |akj +aik |akj | , otherwise
 ij
2

It can be shown that µk µk (A) = A.
2

˜
˜
˜
˜
Two matrices B and B ′ are said to be mutation equivalent, and denoted by B ≃ B ′ , if
each of them can be obtained from the other by a sequence of matrix mutations. It can be
shown that mutation equivalent is an equivalent relation.
˜
˜
Given a seed Σ = (x, B), we say that a seed Σ′ = (x′ , B ′ ) is adjacent to Σ in direction
˜
˜
k if x′ is adjacent to x in direction k and B ′ = µk B ′ . Two seeds are mutation equivalent if
they can be connected by a sequence of pairwise adjacent seeds.
˜
˜
Definition 1.5. Let Σ = (x, B) be a seed with a skew-symmetrizable matrix B, A be subring
with unity in ZP containing all the coefficients p± for all seeds mutation equivalent to Σ The
k
˜
cluster algebra (of geometry type) A = A(B) over A associated with Σ is the A-subalgebra
of F generated by all cluster variables in all seeds mutation equivalent to Σ. A is called the
˜
ground ring of A. the number of rows in the matrix B is said to be the rank of A.
The exchange matrices appear in the seeds in A form an mutation-equivalent class,
denoted by B(A).

1.2

Cluster Algebra Associated with triangulation of
Surface

Triangulation is a useful tool to study the topology of surfaces. Ideal triangulation of bordered surfaces with marked points is of particular interests in cluster algebra. For example,
in [4], the authors construct cluster algebra associated to an ideal triangulation.
Definition 1.6. Let S be a connected oriented 2-dimensional Riemann surface with boundary. Fix a non-empty finite set M of marked points in the closure of S such that every

3

connected component of the boundary has at least one marked point. We call (S, M ) a
bordered surface with marked points if (S, M ) is none of the following:
• a sphere with one or two marked points in the interior of S.
• a disk with one marked point on the boundary, no more than one marked point in the
interior.
• a disk with two marked points on the boundary, no marked point in the interior.
• a triangle with no marked points in the interior.
Definition 1.7. A (simple) arc γ in (S, M ) is a curve in S such that:
• the endpoints of γ are marked points in M ;
• γ does not intersect itself, except that its endpoints may coincide;
• except for the endpoints, γ is disjoint from M and from the boundary of S;
• γ is not contractible into M or onto the boundary of S.
Definition 1.8. A maximal collection of distinct pairwise arcs that do not intersect in the
interior of S is called an ideal triangulation. The arcs of a triangulation cut the surface S
into ideal triangles. The three sides of an ideal triangle do not have to be distinct, i.e., we
allow self-folded triangles. We also allow for a possibility that two triangles share more than
one side.
In the following definition, we extract combinatorial properties from ideal triangulations:
Definition 1.9. We associate to each ideal triangulation T the (generalized) signed adjacency matrix B = B(T ) that reflects the combinatorics of T . The rows and columns of B(T )
4

are naturally labeled by the arcs in T . For notational convenience, we arbitrarily label these
arcs by the numbers 1, . . . , n, so that the rows and columns of B(T ) are numbered from
1 to n as customary, with the understanding that this numbering of rows and columns is
temporary rather than intrinsic. For an arc (labeled) i, let πT (i) denote (the label of) the
arc defined as follows: if there is a self-folded ideal triangle in T folded along i, then πT (i)
is its remaining side (the enclosing loop); if there is no such triangle, set πT (i) = i. For each
△

ideal triangle △ in T which is not self-folded, define the n × n integer matrix B △ = (bij ) by
settings:

△

bij =




1











if △ has sides labeled πT (i) and πT (j)
with πT (j) following πT (i) in the clockwise order;



−1 if the same holds, with the counter-clockwise order;








0

otherwise.

The matrix B = B(T ) = (bij ) is then defined by

B△

B=
△

The sum is taken over all ideal triangles △ in T which are not self-folded. The n × n matrix
B is skew-symmetric, and all its entries bij are equal to 0, 1, −1, 2, or −2.
A quiver is defined as a finite oriented multi-graph without loops and 2-cycles.
Definition 1.10. Let G be a quiver, B(G) = (bij ) is the skew-symmetric matrix whose rows
and columns are labeled by the vertices of G, and whose entry bij is equal to the number of
edges going from i to j minus the number of edges going from j to i.
Definition 1.11. Suppose B is a signed adjacency matrix associated to an ideal triangulation
5

T of a bordered surface with marked points (S, M ), and G is a quiver. If B(G) = B, we say
G is the oriented adjacency graph associated to the triangulation T of (S, M ).
Let B(S, M ) be the mutation equivalent class of B(T ) associated to a triangulation T of
(S, M ). It is proved in [2] that:
Proposition 1.1. B(S, M ) depends only on (S, M ), not on the triangulation T .
Our focus is the class of cluster algebras whose exchange matrices are associated to
bordered surfaces with marked points. Precisely, we say a cluster algebra A is associated to
a bordered surface with marked points (S, M ) if B(A) = B(S, M ). The following theorem is
proved in [2]
Theorem 1.1. Let (S, M ) be a bordered surface with marked points. Assume (S, M ) is not
a closed surface with exactly two marked punctures. Let A be a cluster algebra such that
B(A) = B(S, M ). Then the following hold:
• Each seed in A is uniquely determined by its cluster.
• The cluster complex A is uniquely determined by (S, M ). (i.e. it does not depend on
the choice of p± ).
k
• The seeds containing a particular cluster variable form a connected subgraph of the
exchange graph.

6

Chapter 2
Introduction to Block Decomposition
and s-decomposition
We introduce the main results in this chapter.

2.1

Block Decomposition

In this chapter we consider the properties of triangulations of surfaces with marked points.
Triangulations of surfaces provide a basic tool for study of surface geometry and topology.
An important reference for us is [1] where the authors construct a cluster algebra associated
with an ideal tagged triangulation of a bordered surface with marked points. In [4], they
describe a distinguishing combinatorial property of cluster algebras of finite mutation type
with skew-symmetric exchange matrix. Namely, exchange matrix of such cluster algebra is
block-decomposable, or one of 11 exceptional quiver.
The notion of block decomposition (see Definition 3.1) plays an important role in determining the mutation class of a quiver. In [4], the authors prove that the mutation class of
an adjacency matrix associated to a triangulation of a bordered surface with marked points
is finite (Corollary 12.2 in [4]). In [1], it is proved that an integer skew-symmetric matrix B
is an adjacency matrix of an ideal triangulation of a bordered surface with marked points if
and only if B = B(G) for some block-decomposable graph G.
7

In Chapter 3, we provide a combinatorial algorithm that determines if a given graph is
block-decomposable. Moreover, if a graph G is block-decomposable, the algorithm can also
find all possible bordered surfaces with marked points associated with G.
For a given graph G, we start the algorithm by examining the nodes of largest degree. Note
that by construction (see Definition 3.1), the degree of any node of a block-decomposable
graph does not exceed eight. We examine the nodes of degree eight one by one, and check
the neighborhoods (see Definition 3.2) of the examined node, denoted by o. The set of
decomposable neighborhoods of o we need to check (we denoted it by So , see remark 3.3) is
finite. If So is empty, the graph G is indecomposable and we terminate the algorithm. If o
is contained in a neighborhood N ∈ So , we simplify N in the following way: replace N by a
simpler neighborhood so that the degree of o decreases. We prove that all replacements are
consistent in the following sense: the original graph is block-decomposable if and only if the
new graph is. After the nodes of degree eight are exhausted, we proceed in similar way to the
nodes of degree seven, then, six, five and four. In each step, it is necessary to examine if So
of any node o is non-empty. It is possible that after a few steps of simplification, we obtain
several connected components. The same algorithm can be applied to each component.
Eventually the graph is reduced to one with nodes of degree at most three. The decomposable
neighborhoods of nodes of degree 3 are listed in Section 3.5. Finally, Theorem 3.1 gives a
criterion that determines if a graph that contains only nodes of degree at most three is
decomposable.
Theorem 2.1. Assume that every node in G has degree less than or equal to 3. If each of
the nodes of degree three has a neighborhood as in one of the pictures listed in Figure 3.75
(up to the change of orientations of all edges), then G is block decomposable. Otherwise, G
is indecomposable.
8

Furthermore, the algorithm also provides a list of connected neighborhoods that are
associated to non-unique triangulations, see the following theorem:
Theorem 2.2. If G is a connected block decomposable graph with non-unique decompositions,
it can only be one of the graphs from Figure 3.79, up to the change of orientations of all
edges. Moreover, G has finitely many possible decompositions.
The algorithm also helps to retrieve the triangulations and surfaces that a decomposable
graph G is associated with. We keep track of all neighborhoods that are simplified. After
all nodes of degree higher than three are exhausted, we decompose the graph into blocks.
Each elementary block is uniquely associated to a triangulation of a piece of surface. Gluing
elementary blocks corresponds to a gluing of associated triangulated pieces of surfaces along
arcs of triangulations (see [4]). Therefore, given a block decomposition, we can recover a
triangulated bounded surface associated with the given quiver.

2.2

s-decomposition

With some triangulations of surfaces invariant under finite group symmetries, we associate
quiver whose edges have positive integer weights and call them diagrams Such diagrams are
also associated with skew-symmetrizable matrices with integer entries. An n × n integer
matrix B is said to be skew-symmetrizable if there exists an n × n integer diagonal matrix
D such that BD is skew-symmetric. We call such diagrams or their associated matrices
s-decomposable (see exact definition 4.2).
Mutation and mutation class are also defined for skew-symetrizable matrices. The collection of mutation-equivalent diagrams to a given diagram G is called the mutation class of
G. We say a diagram is mutation finite or has finite mutation type if its mutation class is
9

finite. Each skew-symmetrizable exchange matrix is associated to a diagram with oriented
edges equipped with positive integer weights. Our goal is to establish an combinatorial algorithm that determines if a given oriented graph whose edges are equipped with integer
weights is s-decomposable, thus providing a tool to find if its associated skew-symmetrizable
matrix has finite mutation type. The notion of s-decomposability is a generalization of blockdecomposability for diagrams (see Definition 4.2 and Table 4.1). A skew-symmetrizable exchange matrix is said to be s-decomposable if it can be obtained by gluing both elementary
blocks and 7 additional blocks by the rules in Def. 3.1 and Def. 4.2.
In Chapter 3, we provided an algorithm that determines if G is block-decomposable. As
a corollary, we obtained for any skew-symmetric integer matrix B, an algorithm linear in the
size of B determining if B has finite mutation type. The algorithm we describe in Chapter
4 is a generalization of the one in Chapter 3. The generalized algorithm is inspired by [2],
in which the authors generalize the result of [4] to skew-symmetrizable exchange matrices.
The following results are proved in [2]:
Theorem 2.1.

1. There is a one-to-one correspondence between s-decomposable skew-

symmetrizable graphs with fixed block decomposition and ideal tagged triangulations of
marked bordered surfaces with fixed tuple of conjugate pairs of edges. Conjugate edges
are two edges inside a digon (or monogon) with one of them tagged and the other
untagged.
2. A skew-symmetrizable n × n matrix, n ≥ 3, that is not skew-symmetric, has finite
mutation class if and only if diagram is either s-decomposable or mutation-equivalent
to one of seven exceptional types.
3. Any s-decomposable diagram admits an unfolding (see Definition 4.3) to a diagram
10

associated to ideal tagged triangulation of a marked bordered surface. Any mutationfinite matrix with non-decomposable diagram admits an unfolding to a mutation-finite
skew-symmetric matrix.
According to the theorems above, if G is the diagram associated to a skew-symmetrizable
exchange matrix M , and T is the ideal tagged triangulation corresponding to a particular
s-decomposition Gdec of G, then an unfolding to Gdec defines a skew-symmetric diagram
obtained by gluing of unfoldings of corresponding blocks. We design an algorithm that
determines if a given graph is s-decomposable, and for each possible decomposition, finds
the associated ideal tagged triangulation of bordered surface with marked points. In order
to determine if a given skew-symmetrizable matrix has finite mutation type, it remains to
check if it is of one of the 11 (for skew-symmetric) or 7 (for skew-symmetrizable) types. Since
this requires a bounded number of operations, we obtain a linear algorithm. Moreover, this
algorithm is linear in the size of the given matrix.
Apply the algorithm to Theorem 2.1, we get the following corollary:
Corollary 2.1. Given a skew-symmetrizable matrix B, there exists an algorithm linear in
the size of B to determine if B has finite mutation type.

2.3

Graphs with Non-unique Decomposition and Their
Associated Surfaces

We can recover ideal (tagged) triangulation of bordered surface from a block-decomposition
of a skew-symmetric integer matrix or a s-decomposition of a skew-symmetrizable integer
matrix. Since every block in Table 3.1 and Table 4.1 is associated to a piece of surfaces, the
11

gluing procedure of blocks corresponds to gluing the associated surfaces: gluing two white
nodes means gluing the corresponding sides of the triangulations, (see Figure. 2.1).
1

4
o

1

3

→

o

o o
4

3

2

2

Figure 2.1: Triangulation Gluing

If a decomposable graph has a white node, we will glue a particular piece surface to that
node in the corresponding triangulation to form the boundary, see Figure. 2.2
3
o

→

o

3

1

o o
2

1
1

2

Figure 2.2: Boundary Gluing

By the algorithms in Chapter 3 and Chapter 4, we have the following corollary:
Corollary 2.2. There are only finitely many decomposable connected graphs with non-unique
decompositions.
In Chapter 5, we prove the following corollary:
Corollary 2.3. Suppose G is a decomposable connected graph, then G is either associated
to a unique surface, or isomorphic to the graph in Figure 2.3.

12

Figure 2.3: A block-decomposable graph with non-unique surface

13

Chapter 3
A Decomposition Algorithm for the
Oriented Adjacency Graph of the
Triangulations of a Bordered Surface
with Marked Points

3.1

Definitions

→
For convenience, an edge directed from node x to y will be denoted by − if an edge connects
xy;
node x and y, but the orientation is unknown or irrelevant, we denote the edge by xy.
Definition 3.1. A block is a directed graph that is isomorphic to one of the graphs shown
in Table 3.1. They are categorized as one of the following: type I (spike), II (triangle), IIIa
(infork ), IIIb (outfork ), IV (diamond ), and V (square). The nodes marked by unfilled circles
are called outlets or white nodes. The nodes marked by filled circles are called dead ends
or black nodes. A directed graph G is called block decomposable or simply decomposable if
it can be obtained from disjoint blocks as a result of the following gluing rules: (See [4] for
definition.)
1. Two white nodes of two different blocks can be identified. As a result, the graph
14

I:Spike II:Triangle

IIIa:Infork

IIIb:Outfork

IV:Diamond

V:Square

Table 3.1: Blocks
becomes a union of two parts, and the common node becomes black. A white node
can not be identified with another node of the same block, see Figures 3.2.
2. A black node can not be identified with any other node.
→
→
3. If an edge a := − with two white nodes x, y is glued to another edge b := − with
xy
pq
two white nodes p, q such that x is glued to p and y is glued to q, then a multi-edge is
formed, and the nodes x = p, y = q become black. (Figure 3.1)
→
→
4. If an edge a := − with two white nodes x, y is glued to another edge b = − such that
xy
qp
x is glued to p and y is glued to q, then both edges are removed after gluing, and the
nodes x = p, y = q become black. We say that edges annihilate each other (Figure
3.2).
y

q
+ =
p
x
Figure 3.1: Generating a Multi-edge
y

q

+ =
p
x
Figure 3.2: Annihilating two edges

15

Example

Decomposition A

Decomposition B

Table 3.2: A quiver and its two decompositions
For example, the example quiver in Table 3.2 can be constructed from an infork (IIIa)
and a spike (I) as in decomposition A, or from a spike (I), a triangle(II) and another spike(I)
as in decomposition B.
Remark 3.1. By design, a block-decomposable graph has no loop and all edge multiplicities
are 1 or 2. Therefore, a block-decomposable graph is a quiver.
Remark 3.2. Note that, the color of a vertex is not specified in the original graph, and is
determined only for vertices of blocks of a specified block decomposition. (There might be
several ways to decompose a graph. Hence, a vertex may have different colors in different
decompositions, see Figure 3.2.)
We will assume in the following discussion that G is a finite oriented multi-graph without
loops and 2-cycles.
Proposition 3.1. A graph G without isolated nodes is decomposable if and only if every
disjoint connected component is decomposable.
Proof. It suffices to show that annihilating an edge in a connected graph generates a connected graph. Since we can only annihilate edges in a spike, triangle or diamond block, before
an edge is annihilated, both of its endpoints must be white. Denote these two endpoints by
16

x, y.
• Suppose x, y are endpoints of a spike. Notice that the original graph must be a single
spike. If we annihilate the edge by gluing a triangle, x, y will be connected via the
third node of the triangle. If we annihilate the edge by gluing a diamond, x, y will
be connected via the remaining nodes of the diamond. If we annihilate it by gluing a
spike, the new graph will consist of only two nodes and no edge, a contradiction.
• Suppose x, y are endpoints of a triangle. If we annihilate the edge xy by gluing a spike
or diamond, the remaining two edges of the triangle can not be annihilated, and x, y
will still be connected via the third node of the triangular block. If we glue another
triangle, there are two cases: In the first case, we can annihilate only one edge, namely
xy, and then x, y will still be connected via the third node. In the second case, we
can also annihilate the whole triangle when all three nodes are white. In this case, the
original graph is a single triangular block and the new graph consists of three nodes.
This is again a contradiction.
• Suppose x, y are endpoints of a diamond. Since none of the boundary edges can be
annihilated, after gluing a spike or triangle or another diamond to the edge xy, x, y
will still be connected.

According to the previous proposition, if G is decomposable, we may break connectivity
of a graph in only two trivial cases. In either case, the resulting graph contains isolated
nodes. On the other hand, in a decomposable graph, isolated nodes can only be obtained in
the above manner. Therefore, we can assume from now on that the graph is connected.
17

The following definition is needed in our algorithm:
Definition 3.2. Suppose N is a subquiver of G with all its nodes colored white or black. If
there exists another quiver M with all its nodes colored white or black, such that G can be
obtained by gluing M to N by the rules in Definition 3.1, we say N is a colored subquiver of
G. A neighborhood of o is a colored subquiver of G that contains node o. We say a colored
subquiver N of G is decomposable if there exists another block-decomposable graph G that
contains N as a colored subquiver. A colored subquiver N of G is said to be indecomposable
if any graph that contains N as a colored subquiver is indecomposable. We say a colored
subquiver N is decomposable as a subgraph if N can be obtained by gluing elementary blocks
according to the rules in Definition 3.1, and the color of nodes in N resulted by gluing of
blocks must be compatible with the original color of N .
Remark 3.3. First, note that if G is obtained by gluing a colored subquiver to a neighborhood
of o, no edge of the neighborhood can be annihilated. Secondly, for a given graph G and a
node o, the set of neighborhoods of o in G, denoted by No , forms a partially ordered set by
inclusion. We define three subsets of No as follows:
• Io is the set of all decomposable neighborhoods each of which contains all edges incident
to o.
• Do is the set of all decomposable neighborhoods of o each of which is decomposable as
a subgraph.
• So = {N ⊂ Io ∩ Do | N is minimal}.
For example, consider the graph G in the first picture of Table 3.3. In the first picture,
note that as a quiver, G does not have color on any node, hence the first picture is not
18

considered as a neighborhood. Pictures A,B,C give some examples of neighborhoods of
node o. The neighborhood in picture A belongs to So . The neighborhood in picture B does
not belong to Io . The neighborhood in picture C does not belong to Do . Note that although
C as a graph can be obtained from gluing a spike and two triangles, the two nodes on the
top will be black, which is incompatible with the coloring in picture C.

o

o

o
o
A

G

B

C

Table 3.3: Example of neighorhoods

For a given graph G and a target node o, if So is empty, the graph is indecomposable.
Remark 3.4. In our algorithm we only need to consider neighborhoods from So ,

3.2

Simplification on Nodes of Degree Eight, Seven,
Six and Five

In this section we show when and how to replace the neighborhood of a certain node by
a consistent one which decreases the degree of this node. As a result, the nodes of degree
larger than four are consecutively eliminated. Notice that the highest degree of any node
in a block is 4. Hence the highest degree of any node in a decomposable graph G does not
exceed 8.

19

o

Figure 3.3: Node of degree
8

3.2.1

Nodes of Degree Eight

A node o of degree 8 in a decomposable graph G can only be obtained by gluing a square with
another square (see Figure 3.3). The result is a disjoint connected component. Otherwise,
G is indecomposable.

3.2.2

Nodes of Degree Seven

If o is a node of degree 7 in a decomposable graph G, it must be obtained by gluing a
diamond to a square, see Figure 3.4. The neighborhood is replaced by the one in Figure 3.5.
The following lemma shows that this replacement is consistent.
Lemma 3.1. Suppose a neighborhood of the node o is as in Figure 3.5 and deg(o) = 3. If G
is decomposable, the neighborhood can only be decomposed into a triangle and a spike.
Proof. It is necessary to show that b, c, d form a triangular block in the decomposition and
that a comes from a spike block.
Assume there exists a decomposition. We then claim that the block containing b must
be a triangle. Suppose that the claim is false, and consider the following cases:
1. Suppose that b comes from a fork. Since both edges in a fork contain black endpoints,
they can not be annihilated. Thus, the fork containing b must also contain a or c.

20

However, the directions of a and c are not compatible with the directions of edges in
any fork block. Therefore, b can not be a part of a fork.
2. Suppose b comes from a square block. Since at least one endpoint of any edge in a
square block is black, none of the edges can be annihilated. Thus, the degree of any
corner node is 3, and the central node has degree at least 4. Since the degree of node o
is 3, it can only be one of the corner node in the square. Moreover, since nodes x and p
are not connected, they must both corner nodes on the same diagonal. Therefore, node
y must be the central node. Hence nodes y and p must be connected, a contradiction,
and so b can not come from a square.
3. Suppose that b comes from a diamond. If the diamond does not contain c or d, then
it is necessary to glue d and c together. Since the only white nodes are the endpoints
of the mid-edge, b must be the mid-edge of the diamond. Suppose the diamond does
not contain c. The edges a, d must be both contained in the diamond since the degree
of node o is 3. Hence nodes x, p must be connected, which is a contradiction. Suppose
the diamond does not contain d, then after gluing d to node o, the degree of o must
be at least 4. This again leads to a contradiction. So the diamond must contain d and
c. The directions of b, c suggest that both b, c are in the upper or lower triangle of the
diamond. This forces d to be contained in the diamond. Notice that since the node x
is not connected with p, the other half of the diamond is annihilated. This is again a
contradiction, so the diamond can not contain c. To conclude, b is not contained in a
diamond block.
4. Suppose b comes from a spike, then a, d must come from the same block. Thus, they
form a fork, and so c can not be attached. This proves the claim.
21

Now, the only option is that b comes from a triangular block △1 . If a also comes from △1 ,
the third edge in △1 should be annihilated by another edge, denoted by e. Moreover, both
e and c must be obtained from the same block. Taking into account direction of edges, this
block must be a triangle △2 . Note that the third edge py of △2 is annihilated by an edge f
incident to the node y, so f and d must come from the same block. Again, considering the
directions of edges, this block must also be a triangle △3 . Therefore, the third edge of △3
must be a, which contradicts the assumption that a is an edge of block △1 . Hence a is not
contained in △1 and this triangle is formed by b, c, d, which forces a to be a spike block.
Remark 3.5. After the original neighborhood is replaced by the one in Figure 3.5, assume the
new graph is not decomposable. This means that if the lower triangle and spike described
in Lemma 3.1 are removed, the rest is not decomposable. Therefore, in the original graph,
after the original neighborhood of o is removed, the graph is indecomposable. However, in
this case, the neighborhood of o can only be obtained from gluing a square and a diamond.
Hence the original graph is non-decomposable. This proves that the replacement is consistent. Moreover, all decompositions of the original graph are in 1-1 correspondence with
decompositions of the new one.

o

o

Figure 3.4: Node of Degree 7

3.2.3

Nodes of Degree Six

If o is a node in G of degree 6, there are three cases:
22

p
a

o

b
x

d
y

c

Figure 3.5: Simpliying neighborhoods of nodes with degree 7
1. One possible neighborhood in So comes from a triangle and a square block. (Figure
3.6) Then replace it by the one in Figure 3.7. Lemma 3.1 shows that this replacement
is consistent.
2. The second possible neighborhood in So comes from a fork block (infork or outfork)
and a square block. (Figure 3.8). Then the neighborhood is a disjoint connected
component, since otherwise the graph is indecomposable.
o

Figure 3.6: (Deg 6) Node from triangle and square

o
x
y

z

Figure 3.7: (Deg 6) Replacement

3. The third possible neighborhood in So comes from two diamonds, as illustrated in
Figure 3.9. Note that in Figure 3.9A, if node p and node q are glued together, the result,
if decomposable, is a disjoint connected component, see Figure 3.10A. Otherwise, G is
indecomposable. If p, q are not glued together, the neighborhood is then replaced by
23

o

o

Figure 3.8: (Deg 6) Disjoint Connected components
the graph in Figure 3.11. Lemma 3.1 shows that this replacement is consistent. On the
other hand, gluing nodes p, q together in Figure 3.9B, the mid-edges are annihilated,
as seen in Figure 3.10B. Hence, the degree of o must be 4. This contradicts the fact
that node o has degree 6. In this case, the neighborhood is replaced by Figure 3.11.

p

o

o

qp

A

q

B

Figure 3.9: (Deg 6) Two diamonds glued at one node

A

B

Figure 3.10: (Deg 6) Two diamonds glued at two nodes

Corollary 3.1. Suppose a neighborhood of o is given as in Figure 3.7 and deg(x) = deg(o) =
3. Then this neighborhood can only be decomposed as a triangle plus a spike plus a triangle.
Proof. By Lemma 3.1, the lower part of Figure 3.7 can only be obtained from gluing a spike
and a triangle. For the upper part, the two edges incident to o must come from the same
block. Judging by their directions, the block can only be a triangle. Note that the third
edge of this triangle may be annihilated, as indicated by a dashed line in Figure 3.7.
24

q

p

Figure 3.11: (Deg 6) Simplication for “two diamonds”
Remark 3.6. By an argument similar to the one in remark 3.5, this replacement is consistent.

3.2.4

Nodes of Degree Five

If node o has degree 5, there are three cases:
1. The first possible neighborhood in So comes from a spike and a square, see Figure 3.12.
In this case, we replace it with the neighborhood in Figure 3.5. According to Lemma
3.1, the replacement is consistent.
2. The second possible neighborhood in So comes from a fork and a diamond, see Figure
3.13. Note that the direction of the fork and the diamond can change, so there are 4
subcases. In all of these cases replace the neighborhoods by the one in Figure 3.15.
The replacement is consistent due to Lemma 3.1 and remark 3.5.
3. The third possible neighborhood in So comes from a triangle and a diamond, see Figure
3.14. In similarity with case 2, note that the orientation of both the triangle and the
diamond can also be reversed, and there are 4 possible neighborhoods in this case. Up
to a reversion of directions, the neighborhood is replaced by the one in Figure 3.16.
Lemma 3.1 and Corollary 3.1 ensure that this replacement is consistent.

25

Figure 3.12: (Deg 5) Spike and square

Figure 3.13: (Deg 5) Fork and diamond

3.3

Simplification on Nodes of Degree Four

After the simplifications in the previous section are done, assume now that all nodes in graph
G have degrees at most four. In this section we shall denote the node in consideration by o,
and the nodes connected to it are called boundary nodes. Note that taking into account the
directions of edges incident to o, we can distinguish the following three cases:
A: 4 outward edges, or 4 inward edges.
B: 3 outward edges and 1 inward edge, or 3 inward edges and 1 outward edge.
C: 2 outward edges and 2 inward edges.
We shall consider all the situations above case by case.

o
p

Figure 3.14: (Deg 5) Triangle and diamond

26

Figure 3.15: (Deg 5) Simplification of “fork and diamond”

o

p

Figure 3.16: (Deg 5) Simplification of “triangle and diamond”

3.3.1

Four outward edges or four inward edges.

Without loss of generality, assume that there are four edges directed outwards. If the graph
is decomposable, So consists of only one neighborhood, and the neighborhood is obtained
by the gluing of two forks as in Figure 3.17.

o

+

=

Figure 3.17: “Two forks” and its simplification

3.3.2

Three outward edges and one inward edge, or three inward
edges and one outward edge

Without loss of generality, assume that o is incident to three outward edges and one inward
edge.
Assume that there is only one node, distinct from o and incident to the incoming edge,
that has degree at least two. Denote this node by p:

27

1. The inward edge can not be obtained from a fork. To show this, we use contradiction.
Suppose the edge is contained in a fork block, so o must be the white node in this block.
Therefore, the other inward edge must be incident to o and can not be annihilated.
This contradicts the fact that there is only one inward edge incident to o. Note that
this argument is still true even if p has degree one.
2. Suppose the inward edge comes from a square. Since the degree of o is four, it must be
the center of the square and all four edges are contained in the same square. This is
impossible since none of the edges in a square can be annihilated and the central node
of a square is incident to at least two inward edges and two outward edges.
3. Assume the inward edge is a part of a triangular block. Suppose this triangle does not
contain any of the remaining three outward edges. Then the other edge of the triangle
which is incident to o is annihilated by another edge, denoted by e. In this case, e and
the remaining three outward edges must come from the same block. It can only be a
square with central node o. On the other hand, o is incident to three outward edges
and one inward edge, giving us a contradiction. Therefore, the triangle must contain
one of the outward edges, which forces the remaining two outward edges to be in the
same block. This block must be a fork, see Figure 3.18.
4. Assume that the inward edge comes from a diamond. Node o must be a white node in
the diamond. Judging by the directions of the remaining edges, two of them must be
boundary edges of the same diamond, see Figure 3.19.
5. Suppose that the inward edge comes from a spike, then the remaining three outward
edges come from the same block. However there is no block that contains three outward
edges incident to the same node. Hence in this case, the graph is indecomposable.
28

o

Figure 3.18: (Deg 4) Fork and triangle

y

o

w

Figure 3.19: (Deg 4) Diamond and Spike

o

Figure 3.20: (Deg 4) Fork + Diamond + Spike

In Figure 3.18, replace the neighborhood with the one in Figure 3.7. According to Corollary
3.1 and remark 3.6, this replacement is consistent. Denote the new graph by G′ and the
original graph by G. G′ has one less node of degree 4. For Figure 3.19, lemmas 3.2 and 3.3
show that it has a consistent replacement.
Lemma 3.2. If y, w are not connected by an edge, Figure 3.21 has only one possible decomposition, which is shown in Figure 3.22.

Proof. Consider the edge a. We claim that it comes from a spike block. To justify the claim,
we only need to rule out all other possibilities.
Suppose first that a comes from a fork. Then the other edge of the same fork can not be
annihilated since it has a black endpoint. Hence it must be edge b or c. Assume it is b, then
the degree of b must be one, a contradiction.
29

p
d
y

f

e

b
c

a
o

w

q
Figure 3.21: Diamond and Spike (Labeled)
+

Figure 3.22: Decomposition of diamond + spike
Suppose now that a comes from a square. Since the degree of o is 4, the node o must be
the center of the square, which means edges b, c, f are contained in the same square block.
This is a contradiction, since o must be at least incident to two outward edges and two
inward edges.
Suppose a is contained in a diamond. The degree of node o suggests that o is a white
node in the diamond block containing a. Since the boundary edges of a diamond can not
be annihilated, two of a, b, c, f must be boundary edges. Judging by the directions, the
boundary edges can only be {a, b}, {a, c} or {b, c}. If {a, b} are two boundary edges, then
d must be contained in the same diamond. This means that the node w must be connected
to the node y, which contradicts our assumption. The situation is similar if {a, c} are two
boundary edges. If {b, c} are two boundary edges of the diamond, a is the mid-edge of the
same diamond block. Therefore nodes p, q must be connected with node w, and they must

o

+

Figure 3.23: Replacement of diamond + spike

30

p
d
y

b

f

e
q

o
c

h

a
w

Figure 3.24: Diamond and spike with y and w connected
be black. However, edges d, e are incident to them, again a contradiction.
Finally, suppose a comes from a triangular block. If this triangle does not contain edge f , the
other edge of the same triangle which is incident to o must be annihilated by another edge,
denoted by h. So b, c, f, h come from the same block, which must be a square. However, none
of the edges in a square can be annihilated, which contradicts the fact that h is annihilated.
If the triangle contains f , then b, c must come from the same block, which must be a fork
or a diamond. If it is the latter, the mid-edge must be annihilated. But o is already a black
node once the triangle and diamond are glued together, a contradiction. If it is a fork, the
degree of p must be one. This is again a contradiction.
To sum up, a must be a single spike, and b, c, f come from the same block. This forces the
block to be a diamond.
Lemma 3.3. If w is connected to y in Figure 3.21, then the decomposable graph must have
a disjoint connected component as shown in Figure 3.24.
Proof. According to the previous lemma, there are two possibilities. Either b,c,d,e,f form
a diamond and a, h come from two spikes, or a,b,d,f ,h form a diamond and e, c come from
two spikes. In either case, the neighborhood is a disjoint connected component. Figure 3.24
illustrates the first case. To see the second case, one only needs to change the labeling of
the edges in Figure 3.24.
31

Remark 3.7. The replacement of the graph in Figure 3.22 by the one in Figure 3.23 is
consistent.
Assume now the node incident to the edge directed inwards has degree one.
1. Suppose that the inward edge comes from a spike. We show that the remaining three
edges can not come from one block, and this contradicts decomposability. Indeed,
there is no block that contains a node of degree 3, that is incident to three outward
edges.
2. Suppose the inward edge comes from a fork. Since the degree of o is four, o must be
the white node in the fork. Hence one of the remaining edges is contained in the same
fork. However, their directions are inconsistent with a fork, giving a contradiction.
3. The inward edge can not be obtained from a diamond since every node in a diamond
has degree at least 2.
4. The same argument shows that the inward edge does not come from a square.
5. If the inward edge is obtained from a triangle, then by arguments as in the proof
of Lemma 3.2, the triangle must contain one of the remaining outward edges. The
only possible decomposition is shown in Figure 3.20. The dashed edge can only be
annihilated by a spike, since otherwise the degree of the node will be greater than one.
In this case, the neighborhood is a disjoint connected component.

3.3.3

Two outward edges and two inward edges

Here we will distinguish cases by the number of boundary nodes of degree at least 2. Denote
the number of such nodes by n. For example, if n = 0, it is a 4-star.
32

1

2
o
3

4

Figure 3.25: (deg 4) n=0

1

2
a
d

b
o
c
3

4

Figure 3.26: (deg 4) n=1
3.3.3.1

n=0

The neighborhood consisting of all four edges incident to o can be constructed from gluing
two forks, as shown in Figure 3.25. Also, it can be constructed from gluing two triangles, each
triangle with one edge annihilated. It must be a disjoint connected component, otherwise G
is indecomposable.

3.3.3.2

n=1

Without loss of generality, assume the node 1 incident to an outward edge has degree at
least 2 (Figure 3.26). Then we have the following cases:
1. Edge a does not come from a fork since the degrees of both nodes 1 and o are at least
two.
2. Suppose a comes from a diamond. Since the degrees of nodes 2,3,4 are all 1, they
can not be contained in the same diamond. So node o is a white node of the diamond
before attaching edge b, c, d. Hence at least one boundary edge in the diamond must
be annihilated, which is impossible.
33

1

2

e
a

b

o
c

d

3

4

Figure 3.27: (Deg 4) (n=1) Decomposition illustration
3. Suppose a comes from a square. If o is the central node of the square, edges b, c, d must
be contained in the same square. Hence the remaining 4 nodes must be corner nodes.
Thus, they all have degree 3. This is a contradiction since only node 1 has degree more
than one. So o is a corner node of the square. But then the degree of node o must be
three, which contradicts the fact that the degree of o is four.
4. If a comes from a spike block, b, c, d must come from the same block, which must be a
diamond. Hence, edge d is the mid-edge. However the degree of node 3 is 1, which is
impossible since no boundary edge in a diamond can be annihilated.
5. Assume that a comes from a triangle △. If the other edge of △ incident to o is not b
or c, that edge must be annihilated by another one denoted by e, as shown in Figure
3.27. Thus, b, c, d, e come from the same block, which can only be a square. But the
degrees of nodes 2,3,4 are all 1, which is impossible for nodes in a square block, so
either b or c is contained in the same triangle. Assume that it is b. Notice that node 2
has degree 1. So the edge in △ that connects node 1 and 2 is annihilated by another
edge, denoted by f . If f comes from a spike, the degree of node 1 must be 1 after
gluing, a contradiction. If f comes from a triangle or a diamond, the degree of node 2
has degree at least 2 after gluing, also a contradiction.
To conclude, when n = 1, the graph is indecomposable.
34

3.3.3.3

n=2

In this case, only two boundary nodes have degree at least 2.
Case 1. Assume that the edges incident to the boundary nodes of degree at least 2 have
the same direction. Without loss of generality we assume that both are directed outwards
(nodes 1 and 4 in Figure 3.28 have degree at least 2.) First, suppose either a or d is a
single spike. The remaining three edges must come from the same block, which can only be
a diamond or a square. However, the degrees of nodes 2,3 are both 1, which is impossible.
Second, neither of the edges a or d can be obtained from a fork since both of its two endpoints
have degree at least 2. Third, suppose a comes from a diamond. Then b, c must also be
contained in the diamond. In this case, nodes 1 and 2 must be connected. This means the
degree of node 2 is at least 2, which leads to a contradiction. Next, suppose a or d comes from
a square, then all four edges must be contained in the same square. However, the degrees of
node 2,3 are both one. This is again a contradiction. Last of all, assume a, b come from the
same triangular block and c, d come from another triangular block. Since node 2 has degree
1, the third edge in the triangle containing edges a, b is annihilated, as discussed in the case
when n = 2, this is a contradiction. So in this case, the graph is not decomposable.

1

Case

2
a
d

b
o
c
3

4

Figure 3.28: (Deg 4) n=2 first case
2. Assume now that o is connected to the boundary nodes of degree at least 2 by two edges.
Denote the edge directed inwards by a and the one directed outwards by b (Figure 3.29).
1. For the same reason as in Case 1, neither a nor b comes from a spike block.
35

1

2
a
d

b
o
c
3

4

Figure 3.29: (Deg 4) n=2 second case
2. Neither a nor b comes from a fork since both endpoints have degrees at least 2.
3. Suppose a comes from a diamond. Since the degree of o is 4, it must be a white node
in the diamond. Since no boundary edge in a diamond can be annihilated, b, c must
be boundary edges in the same diamond. Then, nodes 1 and 3 must be connected.
But degree of node 3 is 1 and the boundary edge can not be annihilated, which is a
contradictions.
4. Suppose a comes from a square block. Since degree of o is 4, it must be the central
node of the square. Since none of the edges in a square can be annihilated, a, b, c, d
must all be contained in the same square. But the degrees of node 3,4 are one, a
contradiction.
5. Assume a comes from a triangle △ that does not contain b or c. The other edge in this
triangle that is incident to o must be annihilated by an edge denoted by e. Hence edges
b, c, d, e must be contained in a square block. However, none of the edges in a square
block can be annihilated. Therefore, the triangle must contain either b or c. Using
similar arguments as in section 3.3.3.2, c is not contained in △, so a, b are contained
in △. Then we replace the neighborhood consisting of all four edges incident to o with
the one in Figure 3.30. The replacement operation is consistent by Corollary 3.1.

36

2

1
a

o

b

x

Figure 3.30: Case 2 replacement
3.3.3.4

n=3

Without loss of generality, assume that the node 1 is incident to the edge directed outwards
(denoted by a), and that it has degree one, see Figure 3.31.

1

2
a
d

b
o
c
3

4

Figure 3.31: (Deg 4) n=3

1. Suppose that a comes from a single spike. The remaining edges b, c, d must come from
the same block. The only possible situation is that they come from a diamond (Figure
3.32). Since deg(1)=1, nodes 1,4 are not connected. We will show in Lemma 3.4 that
this neighborhood consisting of the spike and the diamond can be replaced by the one
in Figure 3.33. This replacement is consistent according to Lemma 3.1.
2. Suppose that a comes from a fork. Since deg(o) = 4, o must be the white node in the
fork. Then d is also contained in the same fork. Hence, node 4 must have degree one.
This contradicts the fact that the degree of node 4 is at least two, so a does not come
from a fork.

37

3. Assume a comes from a triangle. According to the argument in section 3.3.2, this
triangle must contain edge b or c Assume that the triangle contains a, b. Since the
degree of node 1 is one and the degree of node 2 is at least two, we obtain a contradiction
by arguments from section 3.3.3.2.
4. Suppose that a comes from a diamond, then the degree of node 1 must be at least 2,
which is a contradiction.
5. Suppose that a comes from a square block. This block must also contain edges b, c, d
since none of the edges in a square can be annihilated. Moreover, o is the central block
of the square, which means node 1 must have degree 3. This is a contradiction.

2
d

4

b

a

c

1

3
Figure 3.32: (Deg 4) Another diamond and spike

G

4

Figure 3.33: G′

3.3.3.5

n=4

In this section, we assume all four boundary nodes have degree at least 2. (Figure 3.34).
We focus our discussion on edge a. By the symmetry of the neighborhood, we can carry the
same argument to any of the edges b, c, d.
38

1

2
a

b
o
c

d

3

4

Figure 3.34: n=4
1. Edge a does not come from a fork since both of its endpoints have degrees at least 2.
2. Assume that a comes from a triangle. Similar to the argument in section 3.3.2, the
triangle must contain b or c. Assume b is contained in this triangle. Then c and d must
come from the same block.
• If c, d are contained in a diamond block, judging by their directions, one of edges
c, d (assume it is d) must be the mid-edge. Thus, besides c, there is another
boundary edge incident to o that comes from the same diamond. Hence, the
degree of o is at least 5, which contradicts our assumption.
• Assume c, d come from a triangle, as shown in Figure 3.35. We replace the neighborhood in Figure 3.34 by the one in Figure 3.36.

1

2
a

b
+
c

d

3

4

Figure 3.35: Two Triangles

Remark 3.8. Notice that in order to perform a replacement, it is necessary to determine
whether a, b or a, c are in the same triangle. This will be discussed later.

39

1

2
a

b

d

c
3

4

Figure 3.36: Simplification of Two triangles

Figure 3.37: Two diamonds with mid-edges glued
3. Suppose that a comes from a diamond. Since the degree of o is 4, it must be a white
node of the diamond. Judging by the directions of edges, there are three cases.
• a is the mid-edge and b, c are the boundary edges. We get a neighborhood as
shown in Figure 3.38. In this neighborhood, the degrees of nodes 2 and 3 are
both 2. We will discuss this case later in this section.
• a, d are the boundary edges and b or c is the mid-edge. We get a neighborhood
shown in Figure 3.39. In this neighborhood, the degrees of nodes 1 and 4 are
both 2.
• a, d are the boundary edges, and the mid-edge is annihilated by another edge e.
So b, c, e come from the same block. It must be a diamond with mid-edge e, see
Figure 3.37. In this case, the neighborhood is a disjoint connected component.
40

2
b

a

1

d

4

c
3
Figure 3.38: Diamond and spike labeled

1
a
b

2

c

3

d
4
Figure 3.39: Another diamond and spike labeled
4. If a comes from a spike, b, c, d must come from the same block. Hence, this block must
be a diamond, see Figure 3.32.
5. Suppose a comes from a square, then a, b, c, f must all be contained in the same square.
Thus, node o must have a neighborhood that comes from a square with o as its central
node. Since the degree of o is 4, the neighborhood is a disjoint connected component.

2
d
4

b

f
e

c

a
1

3
Figure 3.40: Diamond and spike relabeled

Note that Figures 3.38, 3.39, 3.32 represent the same neighborhood except for edge
labeling. For the sake of convenience, we relabel the edges as in Figure 3.40. Note that
the degree of node 1 is at least 2. If node 1 is not connected to node 4, the only possible
decomposition is the one shown in Figure 3.41 (see Lemma 3.4). We apply the replacement
41

as in Figure 3.23. If nodes 1,4 are connected by an edge directed from 1 to 4, Lemma 3.5
shows that there exists a decomposition in Figure 3.43. Thus, we can apply the replacement
as in Figure 3.45. The following lemmas show that our choices of replacements for the
neighborhood in Figure 3.40 are consistent.
Lemma 3.4. In Figure 3.40, assume 4 is neither connected to 1 nor coincides with 1. Assume further that nodes 1,2 and nodes 1,3 are disconnected. If the graph G is decomposable,
then the neighborhood in Figure 3.40 can be decomposed as in Figure 3.41.

+

Figure 3.41: Decomposition of diamond + spike

λ
b
f
e c

d

a

Figure 3.42: Illustration of an impossible decomposition

Proof. We have the following cases:
1. Suppose that a comes from a fork. Since the degree of o is 4, o must be the white node
in the fork. Thus, f is contained in the same fork. Then node 4 must have degree 1,
a contradiction.
2. Suppose that a comes from a triangle, denoted by △. Then there are two cases:
Case 1: △ contains neither b nor c;
42

Case 2: △ contains either b or c
In case 1, consider node o in Figure 3.40. The other edge in △ that is incident to
o is annihilated by another edge, denoted by e. Hence b, c, f, e come from the same
block, which can only be a square block. However, none of the edges in a square can
be annihilated. Therefore, case 1 is impossible. In case 2, assume that △ contains b.
The third edge in △ is annihilated by another edge, denoted by λ (see Figure 3.42).
λ and d must come from the same block, which can only be a diamond or a triangle.
If it is a diamond, λ must be the mid-edge, so node 4 is black. However, edges f, e
need to be glued to 4, a contradiction, so both b, λ belong to a triangle. Since 4 is not
connected to 1, the edge 14 in this triangle must be annihilated by another edge h. So
h, f, e come from the same block, which must be a diamond with h as its mid-edge.
This means that nodes o and 1 are connected by a boundary edge of this diamond.
Thus, the degree of o is at least 5, which contradicts the assumption that deg(o) = 4.
3. Suppose that a comes from a diamond. Since the degree of o is 4, it must be a white
node in the diamond. Since the boundary edges can not be annihilated, and judging
by the directions of the edges, there are only two possible cases:
• a is the mid-edge and b, c are two boundary edges of the diamond.
• a, f are the boundary edges and one of b, c is the mid-edge.
In either case, 1,2 must be connected by a boundary edge and it can not be annihilated,
giving a contradiction.
4. Suppose that a comes from a square, then a, b, c, f must all be contained in the same
square. Thus, the neighborhood is the square. Moreover, nodes 1,2 must be connected,

43

y

w
x

y

x

w

z
Figure 3.43: Illustration of a decomposition of diamond + spike

Figure 3.44: Diamond and two spikes
a contradiction.
5. Suppose edge a comes from a spike. Then b, c, f come from the same block, which
forces the block to be a diamond, see Figure 3.41.

Lemma 3.5. In Figure 3.40, assume that 4 is connected to 1 by an edge directed from 1 to 4.
If the graph is decomposable, nodes 1,2 and nodes 1,3 are disconnected. Then the degree of 4
is 4 and the degree of 1 is 2. In this case, there is a decomposition as in Figure 3.43. Also, it
is possible to simplify the original graph G to G′ (Figure 3.45), and G is decomposable if and
only if G′ is decomposable. If the degree of node 3 is 2, there is an alternative decomposition
as in Figure 3.44. In this case, G is a disjoint connected component.

Proof. The argument differs from the previous one only in the place where a is assumed to
come from a triangle. Notice that 4 is connected to 1. If a, b comes from a triangular block
44

z

G
Figure 3.45: G’
△, the edge 41 must come from another block. This block can be a triangle or a diamond.
In this case, e, f must both come from the other block, which can not be a diamond since
this will force the degree of node 4 to be 5. Recall that we already simplified all nodes of
a decomposable graph so that the degree of any node does not exceed 4. Thus, this block
containing e, f must be a triangle. (The corresponding decomposition is shown in Figure
3.43). In this case, if the degree of node 3 is at least 3, there is another edge incident to
it. The neighborhood can be replaced by the one in Figure 3.45. It is trivial that if G is
decomposable, so is G′ . The converse statement follows from Lemma 3.1.
Remark 3.9. If node 4 coincides with node 1, we have a neighborhood as in Figure 3.46. In
this case, we need to examine nodes p, q.
• If both nodes have degree two, then there are two possible decompositions. Namely, a
diamond plus a spike or two triangles.
• If at least one of p, q has degree more than two, then it must come from gluing two
triangles.
If the node does not have either of the above two neighborhood, the graph is indecomposable.

45

p
a d
o

b
c
q

Figure 3.46: Diamond with two mid-edges

3.4

Distinguishing the Neighborhoods When n = 4

In the previous section, we have discussed all cases when a node with degree 4 is formed. We
also found necessary decompositions in all these cases. However, for a given graph G, when
n = 4, the question still remains when a node o of degree 4 has a neighborhood contained in
So , and which neighborhood it has. For example, in the situation when the neighborhood
may come from two triangles (see Figure 3.35), in order to choose proper replacement, we
must determine whether a, b or a, c are in the same triangle. In this section, we focus on the
case when deg(o) = 4 and n = 4. We want to use only the information that can be directly
derived from the graph:
• How is the node o connected to the boundary nodes? We want to check the direction
of the edges connecting node o and its boundary nodes.
• How are the boundary nodes connected to each other? We want to check if, and how,
some of the boundary nodes are connected to each other.
• If necessary, we want to check if there is any other node that is connected to the
boundary nodes, and how they are connected.

46

First of all, we examine the neighborhoods of o by checking how nodes 3,4 are connected
to node 1.

3.4.1

Node 1 is Connected to Nodes 2 and 3

Assume that nodes 1,4 are connected by an edge denoted by λ and nodes 1,3 are connected
by an edge denoted by γ. Let us consider directions of a, d, λ and a, c, γ. More exactly, we
check if λ is directed from node 1 to node 4 and if γ is directed from node 1 to 3 (see Figure
3.47).

λ
1

2
a

b γ

d

c
3

4

Figure 3.47: Node 1 connected to both 2 and 3

Suppose λ is directed from node 2 to node 1 and γ is directed from node 3 to 1, then
neither a, b, λ nor a, c, γ come from a triangle. Assume a comes from a spike, then b, c, d
come from the same block which must be a diamond. Hence, nodes 2,4 must be connected
and node 2 is a black node before λ is attached. In this case, node 1 must coincide with
node 4. But the directions of λ, γ are prescribed by the decomposition. Hence, the graph
is indecomposable. If a comes from a diamond, the diamond must also contain b, c, λ, γ.
Again, their directions do not fit in a diamond block. To conclude, if a, b, λ or a, c, γ can not
form a triangular block, the graph is indecomposable.
Suppose a, b, λ have the same direction setup as a triangular block, and a, c, γ do not.
We claim that if the graph is decomposable, then a, b, λ must come from a triangular block.
47

Suppose the contrary. Notice that a, c, γ do not come from a triangular block. Edge a comes
either from a spike or from a diamond. In the first case, b, c, d come from the same block
which must be a diamond, and node 2 is connected only to nodes 4 and o. Since node 2
is connected to 1, node 1 must coincide with node 4. But then the direction of γ does not
match the direction of the corresponding edge in a diamond. This is a contradiction. If a
comes from a diamond block, the block can contain b, c, λ, γ or b, d, λ or c, d, γ. But none
of these cases has the directions that match with a diamond block. This again leads to a
contradiction.
−
→
−
→
Suppose λ = 12 and γ = 13. If a comes from a spike, then λ, γ come from the same
block. This block can be a fork or a diamond. But the former is impossible since the degree
of node 2 is 2. If it is the latter, b, c must be boundary edges of this diamond. Thus, the
mid-edge must connect node 1 and o. This forces node 1 to coincide with node 4, as shown
in Figure 3.46. Suppose that a come from a diamond. There are two possibilities. Either
a, b, d come from the same diamond, or, a, b, c come from the same diamond. If it is the
former, node 1 is already black before γ is glued, which is impossible. Suppose it is the
latter. Notice that nodes 2,3 and 3,4 are disconnected unless node 1 coincide with node 4.
Lemma 3.6. Suppose there is an edge directed from node 1 to node 2 and an edge directed
from node 1 to node 3. Furthermore, assume that nodes 2,3 and node 3,4 are disconnected,
and that both nodes 3 and 4 have degree 2. If the graph G is decomposable, then there is a
decomposition of G in which a, b, c, λ, γ come from the same diamond.
Proof. Suppose that the conclusion of the lemma is false.
1. If a comes from a spike, then b, c, d come from the same block which must be a diamond.
Thus, node 3 is a black node of the diamond and γ can not be attached, a contradiction.
48

Figure 3.48: Three triangle
2. If a comes from a triangle, the block could contain either edges b, λ or edges c, γ. In
the former case, edges c, d come from the same triangle △. Since nodes 3,4 are disconnected the third edge of △ is annihilated by another edge, denoted by τ . Hence
τ, γ come from the same triangle, and node 1 is connected to 4. If G is decomposable,
the neighborhood is as in Figure 3.48. Moreover, the degree of node 1 is four and the
degree of node 4 is two. Notice that the degree of node 2 is two, hence the neighborhood is a disjoint connected component. In this case, it can also be decomposed as a
diamond containing a, b, c, λ, γ plus two spikes. In the latter case, the triangle which
contains a also contains c, γ. By the same argument as above, if G is decomposable,
the neighborhood of o is as in Figure 3.48. In this case, it is a disjoint connected
component, and can be obtained by gluing two spikes 14, d to a diamond that contains
a, b, c, λ, γ.
3. Suppose a comes from a diamond. According to the assumption, a, b, c, λ, γ do not
come from the same diamond. Therefore, the diamond containing a must contain b, d
with b as its mid-edge. Then node 1 is black and γ can not be attached, so we get a
contradiction.
4. If a comes from a square, it must contain b, c, d, λ, γ. Moreover, nodes 2,4 and 3,4
must be connected, which again contradicts our assumption.

49

To conclude, under the given assumption, a, b, c, λ, γ come from the same diamond in one of
the decomposition of G.
Remark 3.10. If nodes 2,3 and nodes 3,4 are connected, and the degrees of nodes 2,3 are
both two, node 4 must coincide with node 1. In this case, the neighborhood is shown in
Figure 3.46.
Remark 3.11. In the above situation, if G is decomposable, we may have more than one
decomposition. However, according to the proof of the lemma, there are more than one
decomposition only when the neighborhood is a disjoint connected component. We list all
such disjoint connected components in Figure 3.79. If the whole graph coincides with such
a disjoint component from this list we know already all the possible decompositions and we
do not need to do simplifying replacements. On the other hand, if a decomposable graph
does not coincide with any of the graphs in Figure 3.79, then the decomposition is unique.
Next, we examine the connectivity between node 4 and nodes 2,3.
Assume node 4 is connected to both nodes 3 and 2, see Figure 3.49. If nodes 3,4 are
connected by an edge directed from node 3 to node 4, relabel the indices of the nodes in
the following way: 4 → 1, 3 → 2, 2 → 3 and 1 → 4. Then apply the previous argument.
It is similar if nodes 2,4 are connected by an edge directed from node 2 to nodes 4. Hence,
without loss of generality, assume that edge 24 is directed from node 4 to 2 and edge 34 is
directed from node 4 to 3. If none of the nodes in G (except for node o) is connected to any
of the nodes 1,2,3,4, then it is a disjoint connected component.
Suppose we can find a node x which does not coincide with o that is connected to some
of the nodes 1,2,3,4. We check if there is any node among 1,2,3,4 that is connected to
x. Assume x is connected to only one of 1,2,3,4. Without loss of generality, assume x is

50

1

λ

4

2
γ
3

Figure 3.49: node 4 connected to 2 and 3
connected to 1 by an edge denoted by τ . (Notice that x may be connected to nodes in the
graph other than 1,2,3,4). In this case, if edges a, b come from the same triangle, then edges
c, d come from another triangle, denoted by △1 . Moreover, τ, γ come from the same block,
which must be a triangle △2 . Because x is only connected to one of the nodes 1,2,3,4, the
third edge of △2 is annihilated by another edge, denoted by η. However, node 3 is already
black after gluing △2 to △1 , a contradiction. Hence, edges a, c come from the same triangle
and b, d come from the same triangle. Therefore, edges τ and λ come from the same block,
which is impossible.
Assume that there is a node x which does not coincide o that is connected to only two
nodes of the nodes 1,2,3,4. Notice that x may be connected to nodes other than 1,2,3,4.
Up to a relabeling of indices, there are two possible situations: Either x is connected to
nodes 1,4 or to nodes 1,3.
First, suppose x is connected to nodes 1,4 by edges τ, η respectively. If a comes from a spike,
then τ, λ, γ come from the same block which is a diamond. Judging by the directions of λ, γ,
τ must be the mid-edge. Therefore, node x must coincide with node o. This contradicts our
assumption.
Suppose a comes from a diamond. Since the degrees of node 1 and o are at least 4, a must
be the mid-edge. Therefore, the diamond must contain λ, γ, b, d. Moreover, the degrees of
node 2,3 must be two, a contradiction.
51

We can also rule out the possibility that a comes from a square since both its endpoints have
degree 4. Thus, a must come from a triangle. Otherwise, G is indecomposable. Suppose
a, τ come from the same triangle, then the third edge of this block is annihilated by another
edge, denoted by δ. Hence δ, η, b, c, d come from the same block, which is impossible. If a, b
come from the same triangle, then c, d come from another triangle, denoted by △1 . Thus,
τ, γ come from the same block, which must be a triangle, denoted by △2 . Notice that its
third edge is annihilated since x is connected to only two of the nodes 1,2,3,4. But this is
impossible since node 3 is already black after gluing △1 to △2 . The similar argument shows
that a, c can not come from the same triangle. Thus, the graph is indecomposable when x
is connected only to nodes 1,4.
Assume that x is connected to nodes 1,3 by edges τ, η respectively. If a, c come from the
same triangle, then b, d come from another triangle, denoted by △1 . Thus, τ, λ come from
another block. This block can not be a diamond since λ must then be the mid-edge and the
boundary edge x2 is annihilated, which is impossible. Hence this block must be a triangle,
denoted by △2 . Since x is connected only to two of nodes 1, 2, 3, 4, the third edge of △2 is
annihilated. However, node 2 is already black after gluing △1 to △2 . This is a contradiction.
Therefore if G is decomposable, a, b must come from the same triangle and c, d from another
triangle. Apply the corresponding replacement as in Figure 3.36.
Assume x is connected to at least three of the nodes 1,2,3,4. Up to an index relabeling,
there are two cases: either x is connected to nodes 1,2,3 or x is connected to nodes 1,3,4.
Suppose x is connected to nodes 1,3,4 by τ, ρ, η respectively. Assume that a, b come from
the same triangle, then c, d come from one triangle too. Thus, η, 24 come from the same
block, which must be a triangle, and so node x and node 2 must be connected according
to previous argument. The argument is similar when a and c come from the same triangle.
52

x
ξ

τ
1
η

λ

4

2
ρ
γ
3

Figure 3.50: x connected to all four nodes
In both cases, node o is contained in a neighborhood in So which is a disjoint connected
component, see Figure 3.50. Otherwise, G is indecomposable.
Assume x is connected to nodes 1,2,3 by τ, ξ, ρ respectively. Assume that a, b come from
the same triangle, then c, d come from another triangle, denoted by △1 . Therefore, τ, γ, ρ
must come from the same triangular block, denoted by △2 . Notice that node x is black after
gluing △1 to △2 , node x and node 4 must be connected by the third edge of △2 . Similarly,
assume that a, c come from the same triangle, we will get the same neighborhood (see Figure
3.50). In this case, the neighborhood is a disjoint connected component, Otherwise, the graph
is indecomposable.
Assume next that node 4 is connected only to one of nodes 2,3.
Suppose node 4 is connected to node 3. In this case, if edge 34 is directed towards node 4,
−
→
then edges c, d, 34 can not form a triangular block. This means edges b, d and edges a, c must
come from two triangles, otherwise the graph is indecomposable. By assumption, nodes 2,4
are not connected, hence the edge with nodes 2,4 as its endpoints must be annihilated by
another edge, denoted by η. Hence, η, λ come from the same block which must be a triangle.
−
→
So node 4 is black before attaching edge 34. This is a contradiction. In this case, the graph
is indecomposable.
−
→
If edge 34 is directed towards node 3, there are two possibilities: edges c, d, 43 form a
53

2 1

2

3 4

1

3

o
4

B

A

Figure 3.51: Color matters
triangular block or edges b, d come from a triangle △.
Suppose it is the latter case, the edge of △ that connects nodes 2,4 is annihilated by another
−
→
edge τ . This forces edges τ, 43, λ to form a block, which is impossible. So edges c, d, 34 form
−
→
a triangle. Otherwise, the graph is indecomposable. Hence, edges c, d, 43 form a triangular
block. We apply the same replacement as in Figure 3.36.
Finally, assume that nodes 3,4 and nodes 2,4 are disconnected. Then one edge of the
triangular block that contains edge d is annihilated by another edge, denoted by τ . If a, b
come from the same triangle, then τ connects nodes 3,4. Therefore, γ, τ must form a triangle,
which means that nodes 1,4 must be connected and nodes 2,3 are disconnected. Similarly,
if b, d come from a triangle, nodes 2,4 must be connected by τ , Thus, nodes 2,3 must be
disconnected and nodes 1,4 are connected. (Figure 3.51). Notice that in picture A, node 2
may have degree larger than two, and in picture B, node 3 may have degree larger than 2.
Thus, it suffices to examine the degrees of nodes 2,3 to determine whether edges a, b or edges
a, c come from a triangular block, and then apply the corresponding replacement. To be more
precise, if degree of node 2 is at least 3, node o is contained in a neighborhood in So as shown
in picture A; if the degree of node 3 is at least 3, node o is contained in a neighborhood in
So as shown in picture B; if both nodes 2,3 have degree 2, either decomposition is possible,
and the neighborhood is a disjoint connected component.

54

3.4.2

Node 1 is Connected to Node 2, But Disconnected from
Node 3

Assume that nodes 1,2 are connected by an edge λ, but nodes 1,3 are not connected. If λ
is directed from node 2 to node 1, then a, b, λ do not form a triangular block. Moreover, a
does not come from a diamond. If a comes from a spike, b, c, d must come from a diamond
and node 4 is connected only to nodes 2,3. By assumption, nodes 1,2 are connected,
node 1 must coincide with node 4. This means nodes 1,3 are connected, which contradicts
our assumption. Therefore, a must come from a triangle that does not contain b, λ, hence
the block must contain c. The third edge in that triangle is annihilated by another edge,
denoted by τ . Moreover, τ is directed from node 3 to node 1. Thus, τ, λ come from the
same block. However, there is no such block with such directions, so in this case the graph
is indecomposable.
Assume next that λ is directed from node 1 to node 2.
If a comes from a spike, b, c, d come from the same block, which must be a diamond. Since
nodes 1,2 are connected, node 1 must coincide with nodes 4. Therefore nodes 1,3 are
connected, a contradiction.
Suppose a comes from a diamond. Note that the degree of node o is four, it must be one
endpoint of the mid-edge. Taking into consideration the directions of a, b, c, d, there are three
cases.
• a is the mid-edge of the diamond. In this case, node 2 must be contained in the same
diamond. Since node 2 is not an endpoint of the mid-edge, it must have degree two, a
contradiction.
• b is the mid-edge of the diamond. In this case, d must be contained in the diamond.
55

Therefore, nodes 3,4 are disconnected. Moreover, the degrees of nodes 1 and 4 are
both two.
• c is the mid-edge of the diamond. In this case d must be contained in the diamond,
and nodes 1,3 must be connected, a contradiction.
Lemma 3.7. Assume that nodes 1,2 are connected by edge λ directed from node 1 to node
2, nodes 1,3 are disconnected, nodes 2,4 are connected by an edge directed from node 4 to
2, and that the degrees of nodes 1,4 are two.
(1) If G is decomposable and nodes 2,3 are disconnected, then a comes from a diamond
containing a, b, d, λ and c comes from a spike.
(2) Assume nodes 2,3 are connected by an edge directed from node 2 to 3:
(a) If the degree of node 3 is two, then o is contained in a neighborhood in So , and
this neighborhood is a disjoint connected component.
(b) If the degree of node 3 is at least three, then the graph is not decomposable.
Proof. (1): Suppose nodes 2,3 are disconnected and the statement is false.
It is easy to rule out the possibility that a comes from a square or a fork.
If a comes from a spike, b, c, d comes from a diamond and node 2 is black. Thus, λ can
not be attached unless node 1 coincides with node 4. Thus the degree of node 1 is four.
This contradicts the assumption that degree of node 1 is 2. Suppose edge a comes from a
diamond. Since the statement is false, the diamond must contain a, b, c. Hence node 1 must
be connected to node 3, which is a contradiction to our assumption.
If a, b come from a triangle, c, d also come from a triangle denoted by △. Thus, the third
edge of △ is annihilated by another edge, denoted by η. Hence η, 24 come from the same
56

block, which must be a triangle. Thus, node 2,3 must be connected, a contradiction.
If a, c come from a triangle, then the third edge of this triangle is annihilated by another
edge, again denoted by η. Hence η, λ must come from the same block, which must be a
triangle. Hence nodes 2,3 must be connected, a contradiction.
(2): Assume nodes 2,3 are connected by an edge directed from node 2 to 3. It suffices
to assume that a comes from a triangle or a diamond. Suppose a comes from a triangle,
by a previous argument, all nodes in this neighborhood must be black, which proves (a). If
a comes from a diamond, the degree of node 3 is three. The only possibility to obtain a
decomposition is to glue a triangle or diamond on nodes 2,3. In either case, the degree of
node 2 is larger than 4. This contradicts our assumption in the section that the degree of
any node of G is at most 4. Hence the graph is indecomposable, and it proves (b).
Suppose node 1 or node 4 has degree at least three, then a does not come from a diamond.
Moreover, we can rule out the possibility that a comes from a square, since this will force
−
→
node 1 to be connected to node 3 with an edge 13. Hence a must come from a triangle.
There are two cases: (1). edges a, b are in the same triangle; (2). edges a, c are in the
same triangle. In the first case, edges c, d are in the same triangle. In this case, apply the
same replacement as in Figure 3.36. In the second case, edges b, d are in the same triangle.
Denoted the triangle containing edges a, b by △. The edge in △ that connects nodes 1,3
is annihilated by another edge, denoted by λ. Thus, γ, λ come from the same block, and it
must be a triangle. This means that nodes 2,3 are connected. Moreover, in this case, nodes
2,4 must be connected by an edge directed from node 4 to 2 and nodes 1,2,3 are black.
Notice that nothing has been glued to node 4 yet, this fact is used to distinguish the second
case.

57

2 1

1

2

34

3

o
4

Figure 3.52: Color matters, again
Lemma 3.8. Suppose that graph G is decomposable and node 1 is connected to node 2 by
−
→
an oriented edge 12. Assume further that nodes 1,3 are disconnected:
(a) Suppose nodes 2,4 and nodes 2,3 are connected. If the degree of node 4 is at least
3, then a, c come from one triangle and b, d come from another triangle. If degree of
node 1 is at least 3, then a, b come from the same triangle and c, d come from the same
triangle (Figure 3.52). If the degrees of both nodes 1 and 4 are 2, then o is contained
in a neighborhood in So , and this neighborhood is a disjoint connected component.
(b) If nodes 2,4 or 2,3 are disconnected, then a, b come from one triangle, and c, d come
from another triangle.

Proof. According to the previous argument, it suffices to prove (a). Suppose nodes 2,4 and
nodes 2,3 are connected. If a, b come from one triangle, then c, d come from another triangle.
Moreover, edges 24, 23 must come from the same block, which must be a triangle. The third
edge of this triangle annihilates 34. Therefore, node 4 have degree 2. so, if the degree of node
4 is at least 3, a, c must come from one triangle. Otherwise, the graph is indecomposable.
The rest of part (a) follows from the previous argument.

58

3.4.3

Node 1 is Disconnected from Nodes 2,3

Assume that neither nodes 1,2 nor nodes 1,3 are connected. Without loss of generality, we
can assume that neither nodes 3,4 nor nodes 2,4 are connected. Otherwise, we can relabel
the indices of boundary nodes and apply the previous argument.
Assume that a, b come from the same triangle. Then the third edge of it is annihilated
by another edge, denoted by λ. This edge λ can be a part of a spike, a triangle, or the
mid-edge of a diamond block. If it comes from a triangle or a diamond, nodes 1, 2 must both
be connected to another node x. Conversely, it is possible to determine whether a, b or a, c
come from the same triangle by considering nodes connecting some of the nodes 1,2,3,4.
Suppose none of the nodes 1,2,3,4 is connected to any other node except for o, then the
neighborhood is a disjoint connected component.
Assume that nodes 1,4 or 2,3 are both connected to the same node x. We also assume that
vertex x is distinct from nodes 1,2,3,4, and o. Without loss of generality, assume nodes 1,4
are connected to x. Let α := 1x and β := 4x. If a, d come from the same block, it must be a
diamond. Hence b, c come from another diamond. Since the degree of o is 4, the mid-edges
of these two diamonds annihilate each other. Then the neighborhood is a disjoint connected
component, see Figure 3.37. If we rule out this case, a, d must come from two blocks. By
the previous argument, neither a nor d comes from the a diamond. Thus, they must come
from triangular blocks. Moreover, the triangle that contains a must contain c or b. Without
loss of generality, assume c is contained in such triangle △. Then the third side of △ is
annihilated by another edge, denoted by τ . Similarly, b, d come from another triangle △1 .
The third edge of △1 is annihilated by an edge denoted by η. Then α, τ come from the
same block, which must be a triangle. If node 3 and x are not connected, the third edge of

59

α

1

2

x

o
β

3

4

Figure 3.53: Two diamond with mid-edges glued
1

2
2
1

x

o
o
4

x

3
3

4

Figure 3.54: Decomposition of glued diamonds
the triangle containing α, τ must be annihilated. This is impossible since node 3 is already
black. Therefore, in this case, the graph is indecomposable. If nodes 3 and x are connected
by an edge γ, then α, τ, γ form a triangle if their directions match a triangle, otherwise, the
graph is indecomposable. Notice that β, η must come from the same block. Thus, it must
be a triangle if their directions match, otherwise, the graph is indecomposable. In this case,
nodes x,2 must be connected, and the neighborhood is a disjoint connected component, see
Figure 3.53. In this case, there is an alternative decomposition, see Figure 3.54.
Assume next that x is connected to nodes {1,2} (resp. {1,3},{3,4},{2,4}), we claim
that a, b (resp. a, c, c, d, b, d) come from one triangle, therefore c, d (resp. b, d, a, b, a, c) must
come from another triangle.
Assume that nodes 1,2 are connected to node x and that a, b do not come from the
same triangle in any decomposition of G. Denote α := 1x, β = 2x. Notice that from the

60

previous argument, a does not come from a spike, a fork, a diamond or a square. So it must
be contained in a triangular block △. If △ contains α, then the third edge is annihilated
by another edge, denoted by τ . Hence, τ, b, c, d come from the same block which must be a
square, also nodes o, x must be colored white in that block. This is impossible, so △ does not
contain α, and therefore must contain c. Then the third edge must also be annihilated by
another edge, again denoted by τ . In this case, τ, α must come from the same block, which
must be a triangle △1 . If nodes 3 and x are connected, we will get a neighborhood similar to
the one in Figure 3.53. As we already know, there is an alternative decomposition in which
a, b come from the same triangle. If nodes 3 and x are not connected, then the third edge of
△1 is annihilated by another edge. However, node 3 is already black after gluing △1 . This
means the third edge of △1 can not be annihilated. This is a contradiction. Therefore, a, b
come from the same triangle in a decomposition of G. Otherwise, G is not decomposable.
Remark 3.12. If x is connected to nodes 1,2 and the graph is decomposable, either G has
a unique decomposition in which a, b comes from a triangular block and c, d comes from
another, or G is the graph as in Figure 3.53.

3.5

Simplification on Nodes of Degree Three

Assume the neighborhoods of nodes of degree at least 4 are all simplified, and every node in
the graph has degree at most 3. We focus on the nodes of degree 3.

3.5.1

All edges have the same direction.

Without loss of generality, assume that the edges are all directed outwards, (see Figure 3.55)
Suppose one of them (denoted by a) comes from a triangle. Since deg(o)= 3, and neither of
61

the remaining two edges comes from the same triangle, the incoming edge incident to o in
the same triangle must be annihilated. Denote this edge as e. Then e must be annihilated
by an outward edge from another block. This block must contain the remaining outward
edges b and c. But no such block exists, a contradiction. Hence edge a is not contained in a
triangular block. By symmetry, none of the three edges comes from a triangle.
If one of them comes from a fork, one of the remaining two edges must also belong to the
same fork. Thus, the third edge must come from a single spike. (Figure 3.56) Otherwise,
the graph is indecomposable. Replace the neighborhood with Figure 3.57. By Lemma 3.1,
this replacement is consistent.

3

c
a

1

b

2

Figure 3.55: Three edges going outwards

=

+

Figure 3.56: Decomposition of three outgoing edges

Figure 3.57: Two outgoing and one incoming

Remark 3.13. In order to apply the replacement, we need to determine which two edges
come from a fork. This can be done by checking the degrees of boundary nodes. If one of
62

the boundary nodes has degree more than 1, the corresponding edge must come from a spike
and the remaining two edges form a fork. If all boundary nodes have degree 1, we have a
disjoint connected component and the decomposition is non-unique. If at least two of the
boundary nodes have degrees more than 1, the graph is indecomposable.
If one of the edges, denoted by a, comes from a diamond, denoted by ♦, then one of the
remaining nodes, denoted by b, must come from the same diamond. Thus the third edge c
is not contained in the same block. Since the degree of o is 3, the mid-edge in ♦ must be
annihilated by another edge, e say, directed away from o. Thus, c, e come from the same
block. Since the degree of o is 3, the block containing c, e must be a triangle. However, the
directions of these two edges do not match a triangle. This is a contradiction.
To conclude, if all three edges incident to a node are all directed inwards or outwards
and the graph is decomposable, the neighborhood must be obtained from gluing a fork and
a spike.

3.5.2

Two outward edges and one inward edge

Assume edge a is directed inwards with nodes 1 and o as endpoints, see Figure 3.58. If
a comes from a spike, the remaining two edges must come from a fork. If a comes from a
diamond ♦, the block must contain at least b or c since only the mid-edge can be annihilated
in a diamond. Assume b is contained in this block. The directions of a, b force c to be
contained in ♦, as shown in Figure 3.59. Since all nodes in G has degree at most 3, this
diamond must be a disjoint connected component. Otherwise, G is indecomposable.
Assume a comes from a triangle △, there are two cases:
Case 1: △ contains neither of b, c. Then b, c must come from a diamond or a fork. In the
latter, the remaining edge of △ that is incident to o must be annihilated. This forces o to
63

3

c
a

1

b

2

Figure 3.58: Two outgoing and one incoming labeled

x

a

c
o
b

Figure 3.59: Diamonds as neighborhood of a node with deg 3
be a black node even before b, c are attached. This is a contradiction, so b, c come from a
diamond ♦. Notice that the mid-edge in ♦ should be annihilated by an edge of △, as shown
in Figure 3.60. Simplify the neighborhood by removing the diamond block and leaving the
triangle △ containing a (see Figure 3.61).

Case 2: △ contains one of b, c. Without loss of generality, assume it is b. Then c must
come from a spike.
Let us take a deeper look at Case 2. Assume that the third edge of △ is d. Then there
are two possibilities.
(a.) Edge d is annihilated in the graph.
(b.) Edge d is not annihilated in the graph (Figure 3.62).
2

1
p

o
3

Figure 3.60: Triangle and diamond glued by an edge

64

x
x
o
o

p
Replace by

+

o

p

p

Figure 3.61: Replacement of 3.60
Next, start with case a. There are three ways to annihilate d.
Case (a1): Edge d is annihilated by a single spike, see Figure 3.63. Then replace this
neighborhood by the one in Figure 3.64. By Lemma 3.1, this replacement is consistent.

1
o

2
Figure 3.62: Edge d not annihilated
a
c

o
b

Figure 3.63: Edge d annihilated by a spike

Case (a2): Edge d is annihilated by one edge of a triangle, see Figure 3.65. If p is connected to o via edge c, then this graph forms a disjoint connected component (Figure 3.66).
Otherwise, G is indecomposable. If c does not connect o with p, and there is nothing else
connected to p (deg(p) = 2). Then we replace the neighborhood in Figure 3.65 with the one
in Figure 3.64. If c does not connect p, and deg(p) = 3, as shown in Figure 3.67, there are
two cases:
65

a
o

c

b
Figure 3.64: Replacement of 3.63

a

1

c
3

p
b
2

Figure 3.65: Edge d annihilated by a triangle
• In Figure 3.67, suppose node 3 coincides with node x, edge px is directed from x to p
and deg(1) = 2, the neighborhood in Figure 3.67 coincides with Figure 3.60. In this
case, if graph G is decomposable, the neighborhood is a disjoint connected component.
• Suppose node 3 does not coincide with node x. Then the neighborhood can replaced
by Figure 3.68. It is similar if edge px is directed from p to x. This replacement is
consistent by the previous lemma.
Case (a3): Assume d is annihilated by the mid-edge of a diamond, see Figure 3.69.
Replace the neighborhood by the one in Figure 3.64 as well.
Next, let us discuss case b. If d is not annihilated, there are three subcases:
(b1): Both nodes 1,2 have degree two. By Lemma 3.1, node o must be contained in a

Figure 3.66: Diamond as DCC

66

1

a
c
3

p

x

b
2

Figure 3.67: Two tailed Square

q

p

Figure 3.68: Replacement of 3.67
neighborhood in So that come from a spike and a triangle.
(b2): One of the nodes 1,2 has degree two and the other one has degree three. Assume the
degree of node 2 is two, and the degree of node 1 is three. In this case, o is contained
in a neighborhood as shown in Figure 3.70 or 3.71. In the latter case
(b3): Both nodes 1,2 have degree three. In this case, we count the number of nodes that
are connected to nodes o and 1,2, denoted by n.
• Suppose n = 3, the only possible decomposable situation is given in Figure 3.72.

• Suppose n = 2. One of the exterior nodes is connected to two of the nodes o,1,2.
Denote this node by x. If x is connected to nodes 1,2 (resp. o,1 or o, 2), then
the other exterior node is connected to nodes o (resp. node 2 or node 1). In this
a
o
b
Figure 3.69: Tailed triangle and diamond
67

2
o

1

Figure 3.70: Two tailed triangle
o
2
1
Figure 3.71: DCC
case, edges x1, x2 (resp. xo, x1 or xo, x2 ) come from two spikes and the degree
of x must be two (see Figure 3.73).
• Suppose n = 1. Notice that we assume that the degree of nodes o,1,2 are all
three. So there are two cases, as shown in Figure 3.74. Note that Figure 3.74A is
indecomposable, so the only decomposable neighborhood is Figure 3.74B.
To sum up:
1. Every node in G has degree at most 3.
2. Consider all nodes of degree 3. If all of them fall into the decomposable categories
(Figure 3.75), then either the neighborhood forms a disjoint connected component that can
be easily decomposed, or we can apply the corresponding replacement. If graph G contains
any neighborhood (up to a reversion of edge directions) that is unlisted in Figure 3.75, the
graph is not decomposable.

1
2

o

Figure 3.72: Three tailed Triangle
68

1

2

o

o

1

2
x

x
2

o

x
1

Figure 3.73: Three cases. (n=2)
x

o
2

1

o

2

1

A

B

Figure 3.74: Two cases. (n=1)
Remark 3.14. We can reverse the directions of all edges to get another 14 neighborhoods in
decomposable graph.
Remark 3.15. Note that the degree of node o is not increased in any replacement.
In some of the cases in Figure 3.75, the neighborhood of the target node o contains some
other nodes of degree 3. The algorithm covers the analysis of the neighborhood of these
nodes in the following manner:
• In picture 2 in Figure 3.75, node x has degree 3. Node x is contained in a neighborhood
in Sx that is isomorphic to the one in picture 2 by a complete reversion of edge directions
(node x mapped to node o). Node p in picture 4 is contained in neighborhood in
Sp isomorphic to the neighborhood of o in the same picture by a reversion of edge
directions. Similarly, a neighborhood of node p in picture 6 (resp. node y in 9 and 10)
is also isomorphic to a neighborhood of node o in picture 6 (resp, node o in picture 9
and 10).

69

o

a

x

c

a
c

o

o

b
1

y

2

x

o

b
3

a
o

p

b

o

4
x

5

a

c

b

o

b
o
a

c

p

z
y
7

6
x

p
y
9

8

o

p

a

b

z

c

y

x

x
o

y
10

11
y

x
o

z

o

x

y

c

z
o
13
a
o

y

12
z

x

b
14
Figure 3.75: All decomposable cases for degree 3

70

y

o

x

• Node x in picture 5 of Figure 3.75 is contained in a neighborhood isomorphic to the
one in picture 4. To be more specific, the neighborhoods of x in picture 5 is the
neighborhood of o in picture 4.
• Picture 9 is a part of picture 10. Note the replacement for picture 9 is the same as the
replacement for picture 10. Therefore, whether node o in picture 9 or 10 is examined
first does not affect the result of the algorithm.

3.5.3

Determine the Decomposition

In the previous section, we have found all possible neighborhoods in So for node o of degree
3 in a decomposable graph. In this section, we want to determine if a node o is contained in
a neighborhood in So , and which neighborhood it is. This is done by checking two things:
• The number of nodes (other than nodes 1,2,3 and o) that are connected to some of
the nodes 1,2,3. Denote this the number by n.
• The direction of edges connecting o, its boundary nodes and other nodes that are
connected to nodes 1,2,3
If all three edges incident to o have the same direction, the only possible neighborhood in a
decomposable graph comes from gluing a fork to a spike. Moreover, n is 0 or 1. If n = 1,
there is only one node that differs from o and is connected to nodes 1,2,3. Denote it by x.
If x is connected to node 1 (resp. node 2 or 3), then edge o1 (resp. o2 or o3)comes from a
spike and edges o2, o3 (resp. o1, o3 or o1, o2) come from a fork.
We focus on the case when the node o has one incoming and two outgoing edges. Note that
the remaining case is when there is one edge going away from node o and two edges going

71

towards node o. The latter case can be analyzed by reversing direction of all edges and using
the following argument.
Assume node 1 is incident to the inward edge. Denote edges o1, o2, o3 by a, b, c respectively. By Figure 3.75, n ≤ 3

Suppose n = 0. By the previous discussion, if the graph is decomposable, we can only
have neighborhoods as in Figure 3.76. After reversing all directions, we can get another four
possible cases.
2
3

o

3
o

o
1

2

2

x

a

1

1

c
o
b

Figure 3.76: All Decomposiable case when n=0

Next, suppose n = 1. Denote this node by x. Assume x is connected to all nodes 1,2,3.
There are two cases:
• If deg(1) = 3, edges b, c must come from the same diamond and edge a comes from a
triangle. See Figure 3.77 for directions of edges. Note that it is exactly picture 4 in
Figure 3.75.
• If deg(1) = 2, the neighborhood is a disjoint connected component, there are two
possible decomposition: (1). a comes from a triangular block and b, c come from a
diamond; (2). a, b come from one triangular block, and edges 2p and 1p come from
another triangular block, and edges c and 3p come from two spikes.
Suppose x is connected to exactly two of the nodes 1,2,3. There are three cases:

72

2

1
o

x

3
Figure 3.77: x connected to all three nodes
1. Suppose x is connected to nodes 1,2. x can only be contained in the neighborhoods
as shown in picture 4 or 5 in Figure 3.75. Edges a, b comes from the same triangle.
Similarly, if x is connected to nodes 1,3, edges a, c are in the same triangle.
2. Suppose x is connected to nodes 2,3. None of the pictures in Figure 3.75 contains such
a neighborhood. Hence the graph is indecomposable.
Assume x is connected to exactly one of the nodes 1,2,3. First, suppose x is connected
to node 1 which is an endpoint of an inward edge. Note that nodes 2 and 3 can not be
connected to node 1. Use the argument in the previous section. If the graph is decomposable,
we conclude the following:
• If nodes 1,2 are connected, edges a, b come from the same triangle and edge c comes
from a spike.
• If nodes 1,3 are connected, edges a, c come from the same triangle and edge b comes
from a spike.
• If nodes 2,3 are both disconnected from node 1, edges b, c come from the same fork
and edge a comes from a spike.
Suppose x is connected to node 2. If the graph is decomposable and node 1,2 are
connected, then a, b come from the same triangle. If nodes 1,2 are disconnected, then a, c
come from the same triangle. The criterion is similar if x is connected only to node 3.
73

Next, suppose n = 2, and denote these two corresponding nodes by x, y.
First, check if they are both connected to node 1. If it is this case, neither node 2 or 3 can
be connected to node 1. Moreover, according to the argument in the previous section, we
have two cases: (1). a comes from a spike and b, c come from a fork; (2). a comes from a
triangle. In the second case, x, y must both be connected to nodes 2 or 3 by edges with
compatible directions, and edges a, b (edges a, c) are in the same triangle, see Figure 3.75,
picture 5.
If x, y are not both connected to node 1, check if they are both connected to node 2. If so,
edges a, c can only be obtained from a triangle and b comes from a spike. Since n = 2, there
is no node other than o that is connected to node 1 or 3. Therefore, the neighborhood is as
the one in Figure 3.78. Note that node o is contained in a neighborhood listed in picture 14
Figure 3.75. The argument is similar if x, y are both connected to node 3.

x

a
o
c
b

y

Figure 3.78: n=1 and deg of node 1 is three

Next suppose x, y are not connected to the same node. If the graph is decomposable,
there are the following cases:
• x is only connected to node 1 and y only to node 2. In this case, nodes 1,2 must be
connected and a, b come from the same triangle. It’s similar if x is only connected to
node 1 and y only to node 3.
• x is only connected to nodes 1,2 and y only to node 3. In this case, a, b come from
74

the same triangle. If nodes 1,2 are connected, node o is contained in a neighborhood
as shown in Figure 3.75, picture 13. If nodes 1,2 are disconnected, the neighborhood
is as shown in picture 8 (node p = x).
• x, y are connected to nodes 2,3 respectively. In addition, if nodes 1,2 are connected,
then edges a, b come from the same triangle. The neighborhood is as shown in picture
11. Similarly, if nodes 1,3 are connected, edges a, c come from the same triangle.
Notice that in this case, nodes 2 and 3 can not be connected to node 1 at the same
time, neither can they both be disconnected at the same time.
Last of all, suppose n = 3. Denote the three corresponding nodes by x, y, z. According to
the argument in the previous section, in this case, the graph G is decomposable only if node
1 is connected to node 2 or 3, forming a triangle with the corresponding edges. See Figure
3.72.
Theorem 3.1. Assume G is a connected quiver such that every node in G has degree less
than or equal to three. If each of the nodes of degree three has a neighborhood as in one of
the pictures listed in Figure 3.75 (up to a change of orientations of all edges), then G is
decomposable. Otherwise, G is indecomposable.
Proof. If G is either the graph in pictures 2 or the one in 6 in Figure 3.75, the result is
evident. Suppose G is neither the graph in picture 2 nor the one in picture 6. Apply
replacements to corresponding neighborhoods in Figure 3.75. Denote the new graph by G′ .
Notice that according to Lemma 3.1, if G′ is decomposable, so is G. The replacements for
all neighborhoods in Figure 3.75 contain triangular blocks. Each node of degree three in
G′ has a neighborhood in the form of Figure 3.62 and is obtained from gluing a triangular
block to a spike. Remove all the triangles and the resulting graph is a disconnected union
75

of paths. Note that since all forks have been replaced in the previous steps, all the paths
are obtained by gluing of finitely many spikes in a unique way. Since the new graph has a
unique decomposition, so does the original graph.
As an application of the algorithm we can classify all decomposable graphs with nonunique decompositions:
Theorem 3.2. Any connected decomposable graph G with non-unique decompositions is one
of the graphs from Figure 3.79, up to the change of orientations of all edges in G.

Figure 3.79: Neighborhoods that Have Non-unique Decomposition

76

Corollary 3.2. Suppose G is a finite quiver with non-unique decompositions. If G does not
contain isolated nodes, then it only has finitely many possible decompositions.
Sketch of Proof: Recall that a disconnected decomposable graph G can not be obtained from
gluing a block to a connected decomposable graph unless G contains isolated nodes. If a
finite graph G has infinitely many different decompositions, it would mean that there are
infinitely many decompositions such that the edges in a large portion (not just one edge)
are annihilated and remaining part coincides with graph G. This means that G contains
isolated nodes in the portion where all edges are annihilated.

Lemma 3.9. The decomposition algorithm is linear in the number of nodes in the graph.
Proof. At each stage of simplification, the number of replacements that we need to apply
is no more than the number of nodes in the graph. Moreover, if the replacement is applied
to a neighborhood of a node, the degree of the considered node becomes three. Thus a
replacement reduces the degree of the considered node to three if it is larger than three in
the original graph. Moreover, any node of degree three in the replacement is obtained by
gluing a triangle to a spike, so we do not apply replacement again in the stage when we
consider nodes of degree three. This means replacement is applied at most once to the same
node. To conclude, the number of replacements is less than the number of nodes in the
graph.
In [4], Fomin, Shapiro and Thurston define an operation on quivers called mutation. A
quiver is said to have finite mutation type if its mutation class is finite. It was noticed by
P.Tumarkin that our algorithm provides a fast way to determine when a quiver of size larger
than 10 has finite mutation type (see [1] for details).
77

Theorem 3.3. There exists an algorithm which is linear in number of nodes to check if any
quiver has finite mutation type.
Proof. By the proposition in Section 3.1, we can assume that the given quiver G is connected.
In [1], the author proved that a quiver with finite mutation type is either decomposable or
one of the 11 exceptional types whose size does not exceed 10 (see Theorem 6.1 in [1]). We
apply our algorithm to check if G is decomposable. By the previous lemma, the number
of operations is linear in the number of nodes in G. If the algorithm shows that G is
indecomposable, and the size of G does not exceed 10, we further check if G coincides with
one of the 11 exceptional types in Theorem 6.1 [1]. The last step takes only finite number
of operations, this finishes the algorithm.

3.6

Example

Suppose we have a skew-symmetric matrix:




0
0
0
0 −1 1




1 0 −1 −1 1
0






1 1
0
0 −1 1 


D=



0 1
0
0 −1 0 






0 −1 1
1
0 −1




0 0 −1 0
1
0
D is associated to Figure. 3.80:
Note that largest degree of all nodes is 4. We start with node 2. For convenience, relabel
nodes 1,3,4,5 by nodes a,b,d,c, node 2 by o. Since nodes a,b are connected by edge → ab
78

1
3

2
4

5

6

Figure 3.80: An example
(under new labels) and nodes ac are disconnected, we have a neighborhood as described
in section 3.4.2. By Lemma 3.8, edges → ab, → bo, → oa come from a triangle block and
edges → od, → dc, → co come from another triangle block (under new labels). We apply
corresponding replacements, and get the graph in Figure 3.81:
1

3
5

6

4
Figure 3.81: Step 1

Similar arguments can be apply to the neighborhoods of node 3 and 5. We apply similar
replacements, and get a new graph in Figure 3.82. In the original graph, the node label by a
number in parentheses is glued to the node labeled by the same number without parentheses:
Now all nodes have degree three. The number of operations applied is 3. Note we do
not need to check the additional nodes created by replacements, and we do not check nodes
2,3,5. Hence we only check nodes 1,4,6. According to Section 3.5, there is no neighborhood
that needs to be replaced, and all nodes have neighborhoods that belong to Figure 3.75.
Therefore our original graph is block-decomposable, and the total number of operations is
3 + 3 = 6.

79

1
2
(3)

5

(2)

3
(5)

4

6

Figure 3.82: Step 2
We can also recover the surface associated to matrix D. According to the decomposition,
the associated graph is obtained by three triangle blocks, each associated to a puzzle piece
(see Chapter 5 for correspondence). The associated surface is as Figure 3.83:

1
3
6

2
5

4

Figure 3.83: Associated Surface

80

Chapter 4
The Decomposition Algorithm of
Skew-symmetrizable Exchange
Matrices

4.1

Definitions

In this section, we introduce definitions and a brief description of the algorithm. As in the
last chapter, we denote an edge that connects nodes x, y by xy if the orientation of this edge
→
−
is unknown or irrelevant, − if the edge is directed from x to y, and ← otherwise.
xy
xy
It is proved in [4] that an skew-symmetric exchange matrix has finite mutation type if it
is associated to a decomposable graph or one of the 11 exceptional types. To generalize the
results to skew-skymmetrizable matrix, we need the following definitions:
Definition 4.1. A diagram S associated to a skew-symmetrizable integer matrix B is an
oriented graph with weighted edges obtained in the following way: Suppose B = (bij )n
i,j=1 .
Vertices of S are labeled by [1, . . . , n]. If bij > 0, we join vertices i and j by an edge directed
from i to j and assign to this edge weight −bij bji .
Definition 4.2. If a diagram G can be obtained by gluing both elementary blocks and new
blocks in Table 4.1 by the gluing rules in Definition 3.1 and the following new rules, we say
81

the diagram is s-decomposable:
1. If the diagram has multiple edges containing n parallel edges, replace the multiple
edge by an edge of weight 2n. For example, if we glue two parallel spikes of the same
direction, we get an edge of weight 4 (see Figure 4.1).

Figure 4.1: Edge of Weight 4

2. All single edges have weight 1.

Remark 4.1. If G is obtained by gluing blocks by the above rules, G is associated to a ideal
tagged triangulation of bordered surface with marked points obtained by the gluing of the
pieces of surfaces associated to the blocks, two arcs are glued together iff the corresponding
nodes are glued together in the associated blocks (see [2]).
Remark 4.2. According to the above rules, the weight of any edge in a s-decomposable
diagram can only be 1, 2 or 4. All edges of weight 2 can only be obtained from blocks in
Table 4.1. Moreover, since all edges of weight 2 contains at least one black endpoint, we can
never obtain an edge of weight 4 from edges of weights 2. Moreover, an edge of weight 4 can
only be obtained from IVor by Figure 4.1 or from gluing two edges of the same direction
from elementry blocks.
Definition 4.3. The unfolding procedure is defined as follows (see section 4 in [2]): Suppose
that we have a chosen disjoint index sets: E1 , E2 , . . . , En , with |Ei | = di . Denote m =
n
′
i=1 di . To each matrix B mutation-equivalent to a given skew-symmetrizable m × m

82

Table 4.1: Blocks of Unfolding
New Blocks

Unfolding

Triangulation
u

Ia:

v1

2

u

v

v2

2

u

v

v
II:

IIIa:

IIIb:

2
u

p

2
w

2
2 w
u
2
q
p
2
w 2 u
2
q

u
v1

boundary
v2

u
v1
u

u

w

w
v1
v2

v2
w1
p

q
u

p

w2

q

w2

w1
u

p
w1

w2
u

w1
w2

q

p
q
u

p1

2 2
w 4 p
p

r

q

w1

w2
u

2

u2

p2

u1
q

q

p1
p2
p

r
r

w

p
w

w1
w2

2

2

V:

v2

u

u
IV:

v2

u
v1

Ib:

boundary v1

w
u2
83

u1

u2

matrix B, a skew-symmetric matrix B ′ indexed by

n
i=1 Ei is defined so that the following

conditions are satisfied:
1. the sum of entries in each column of each Ei × Ej block of B ′ equals to bij ;
2. if bij ≥ 0, then the Ei × Ej block of B ′ has all entries non-negative.
Define a composite mutation µi =

′
j∈Ei µj on B . If C is the skew-symmetric matrix

constructed from B satisfying the above conditions, we say C is an unfolding if for any B ′
mutation-equivalent to B, µi (B ′ ) = µ(B ′ ).
A geometric interpretation of mutations on the blocks in Table 4.1 is given in Lusztig’s
[5]. Abusing the notation, we say the new blocks are the foldings of their corresponding
unfoldings. Each unfolding represents an ideal tagged triangulation of bordered surface with
marked points (see pictures in [2], (Table 7.1)). Each of these unfoldings except the last one
corresponds to triangulations with two edges inside a digon (or monogon), one of the edges
is tagged and the other is untagged. This pair of edges are said to be conjugate. Conjugate
edges represent the same vertex in the foldings. Mutation of the folded vertex corresponds
to the flips of both edges in the conjugate pair. Composite flip of the triangulation corresponding to an unfolding diagram is defined as a collection of flips in all edges that represent
vertices in the set Ei . Note that any two flips in a composite flip commute, see Figure 4.2.
In [2], the following theorem is proved:
Theorem 4.1. Any s-decomposable diagram admits an unfolding to a graph arising from
ideal tagged triangulation of a marked bordered surface. Any mutation-finite matrix with
non-decomposable diagram admits an unfolding to a mutation-finite skew-symmetric matrix.
Given an s-decomposable diagram with a fixed decomposition, there is a unique tagged
triangulation of a marked bordered surfaces with chosen tuples of conjugate pairs of edges.
84

v2
Flip v2
v1 v2
Flip v1

v1

Flip v1
v1
v2

v1 Flip v2
v2

Figure 4.2: Composite Flip
This surface can be obtained by gluing pieces of surfaces representing unfoldings of corresponding blocks in the decomposition along edges corresponding to glued white vertices. The
construction is invariant under mutation: mutating the diagram means performing composite flips to the original triangulations. Furthermore, the following theorems are proved in
[2]:
Theorem 4.2. There is a one-to-one correspondence between s-decomposable skew-symmetrizable
diagrams with fixed decomposition and ideal tagged triangulations of marked bordered surfaces
with fixed tuple of conjugate pairs of edges.
Theorem 4.3. A skew-symmetrizable n × n matrix, n ≥ 3, that is not skew-symmetric,
has finite mutation class if and only if its diagram is either s-decomposable or mutationequivalent to one of seven types.
By the previous theorems, to check that a given skew-symmetrizable non skew-symmetric
matrix has finite mutation type, we can first check if it is mutation-equivalent to one of the
seven types of diagrams. If not, we can further check if the associated adjacency graph
is s-decomposable. We develop an algorithm below that determines if a given diagram is
s-decomposable.
Recall Definition 3.2. We generalize it to the following:
85

Definition 4.4. Suppose N is a subgraph of G with all its nodes colored white or black.
If there exists another quiver M with all its nodes colored white or black, such that G can
be obtained by gluing M to N by the rules in definition 3.1 and 4.2, we say N is a colored
subgraph of G. A neighborhood of o is a colored subgraph of G that contains node o. We say a
colored subgraph N of G is decomposable if there exists an s-decomposable or decomposable
graph G that contains N as a colored subgraph. A colored subgraph N of G is said to be
indecomposable if any graph that contains N as a colored subgraph is neither s-decomposable
nor decomposable. We say a colored subgraph N is s-decomposable as a subgraph if N can
be obtained by gluing blocks by the rules in definition 3.1 and 4.2, and the resulting color
of nodes in N coincides with the original color of vertices in N .
Remark 3.3 can be generalized to the following:
Remark 4.3. Note that if G is obtained by gluing a colored subgraph to a neighborhood of
o, no edge in this neighborhood can be annihilated. For a given graph G and a selected node
o, the set of neighborhoods of o in G, denoted by No is a partially ordered set by inclusion.
We define three subsets of No as follows:
• Io is the set of all decomposable neighborhoods each of which contains all edges incident
to o.
• Do is the set of all decomposable neighborhoods of o each of which is decomposable as
a subgraph.
• So = {N ⊂ Io ∩ Do | N is minimal}.
If So is empty, then by definition, the graph containing o is not s-decomposable.
Our goal is to find a combinatorial algorithm which determines if a given graph is sdecomposable. According to remark 4.2, we can determine if a graph contains blocks from
86

Table 4.1 by locating edges of weight 2 and analyzing their neighborhoods. We differ cases
by the number of edges of weight 2 that are incident to the considered node o. Denote
this number by n. According to the rules of gluing, n is at most 4 for any node in an
s-decomposable graph. If o is not incident to any of edges of weight two, we skip this node.
Therefore, n = 1, 2, 3 or 4. Starting with any node o with n = 4, we check if So is non-empty
by examining the following information that can be directly observed from the graph: degree
of o, degree of the nodes that are connected to o by one edge, and the number and directions
of the edges between node o and the nodes connected to o. If So is empty, the graph is not
s-decomposable. If o is contained in a neighborhood in So , we replace the neighborhood
by another one which is consistent in the sense that the new graph is s-decomposable if
and only if the original one is. The new neighborhood does not contain any edge of weight
2. After all nodes with n = 4 are exhausted, we proceed to the nodes with n = 3, 2, 1 (in
this exact order). Finally, we get a graph that contains only edges of weight 1 and 4. The
new graph is s-decomposable if and only if it is decomposable (see [6]). Then we apply the
algorithm from [6] to determine it the graph is decomposable. Since all replacements are
consistent, we can determine if the original graph is s-decomposable.

4.2

Algorithm

In [6], it is proved that we can assume that the graph is connected when only blocks in
Table 3.1 are used. If the graph is s-decomposable, it is easy to see that we can make the
same assumption as well. In fact, except II, none of the edges can be annihilated by gluing
a block from Table 4.1 to any graph. If IIis glued to an existing graph, causing uw to be
annihilated, nodes u, v are still connected via uv and vw. Therefore, gluing new blocks will

87

not break connectivity.
Let U be the collection of both old and new blocks. In order to find So of a node o,
it suffices to check if node o has a neighborhood that is isomorphic to some graph in U or
obtained by gluing two blocks from U. By checking all nodes in U, we analyze the results in
Table 4.2-4.7.
If any of the neighborhoods in U is a disjoint connected component, the algorithm stops.
If the neighborhood may not be a disjoint connected component (DCC), we apply suitable
replacement as suggested in the tables below. Note that we need those replacements to be
consistent, i.e. the original graph is s-decomposable if and only if the new graph is. The
consistency of all replacements can be checked by exhausting analysis of all neighborhoods
in U and Lemma 1 in [6].

4.2.1

n=4

We have the following two situations:
Table 4.2: n = 4
A

Decomposition
Degree of o
Replacement

4.2.2

B

4
DCC

4
DCC

n=3

We have the following eight situations:

88

Table 4.3: n = 3
A1

A2

3

3

B1

B2

Degree of o

3

3

Replacement

DCC

DCC

C1

C2

4

4

D1

D2

Degree of o

5

5

Replacement

DCC

DCC

Decomposition
Degree of o

Replacement

Decomposition

Decomposition
Degree of o

Replacement

Decomposition

89

In this case the degree of the considered node can only be 3, 4 or 5, otherwise the graph
is not s-decomposable. For a given graph G, to determine neighborhood o of what type is
considered, we examine the degree of o.
First suppose the degree of o is 3. We only need to consider A1,A2,B1,B2. We call the
nodes connected to o by an edge boundary nodes. If one of the boundary nodes, denoted by
x, is connected to the remaining two by edges of weight 1, o can only be contained in A1
or A2. Note that in either cases, the degree of x is no less than 3, and the degrees of the
remaining two boundary nodes are 2. If only two of the boundary nodes are connected, o
can only be contained in B1 or B2. In both cases, the neighborhoods are disjoint connected
components.
Second, suppose the degree of o is 4. Node o can only be contained in C1,C2, otherwise
the graph is not s-decomposable. Note that in this case, one boundary node is connected to
o by an edge of weight 1. Denote this node by x. The remaining three boundary nodes are
connected to o by edges of weight 2, two of them are connected by an edge of weight 4, the
third one is connected to x by an edge of weight 2. Moreover, the degree of x is no less than
2, the remaining boundary nodes all have degree 2.
Finally, suppose the degree of o is 5. In this case, o can only be contained in D1,D2,
otherwise the graph is not s-decomposable. In either case, the neighborhood is a disjoint
connected component.

4.2.3

n=2

We have the following 13 situations:

90

Table 4.4: n = 2
A

B

o
2

2

y

x

Decomposition
Degree of o

≥2

2

Replacement
C

2

o o
+

2

o o
+

2

2

o o
+

2

2

Decomposition

Degree of o

2

Replacement

DCC
D1

D2

y
2

2
2
Decomposition
Degree of o

z

y
2
2

o +o

x

3

z

o +o
3

91

2
x

cont’d
x

x

Replacement
E1

E2

y

y
2

w

o

+

2

2

x

o

w

o

+

2

2

2

z

Decomposition

x

o
z

Degree of o

4

4

Replacement

DCC

DCC

E3

E4

y

y
2

w

o

+

2

2
x

o

w

o

+

2

2

2

z

Decomposition

x

o
z

Degree of o

4

4

Replacement

DCC

DCC

F1

F2

2
2
Decomposition
Degree of o

2

2

o+ o

2
2

x

2

2
o+ o

2
5

5

92

2
x

cont’d

Replacement
F3

2
2
Decomposition
Degree of o

F4

2

2

o+ o

2
2

x

2

2
o+ o

2
x

2
5

5

Replacement
To determine if the considered node o is contained in any of the neighborhoods in Table
4.4, we consider the degree of o. Note that when n = 2, the degree of node o in Table 4.4
takes only 2, 3, 4 or 5, otherwise, the graph is not s-decomposable.
If the degree of o is 2, o in s-decomposable graph can have only neighborhoods of type
A,B,C, (see Table 4.4.) In this case we denote the other endpoints of the edges of weight 2
by x, y.
• If x, y are not connected by an edge, the graph is s-decomposable in two cases. First,
the neighborhood can be obtained by gluing {Ia,Ib}, or two Ia, or two Ib, as shown
−
in case C; second, the neighborhood can be obtained from annihilating edge ← in II,
xy
as shown in case A. To determine how the neighborhood is obtained, note that in the
first case, the neighborhood is a disjoint connected component, and in the second case,
−
the edge ← can be annihilated by an edge from a spike, a triangle or the mid-edge
xy
of a diamond. Suppose the degrees of nodes x, y are both 1. If edge xo and yo are
both directed away from or towards node o, then the neighborhood is obtained in the
93

way shown in the second or third picture in case C, otherwise the graph is not sdecomposable. Suppose two edges have different orientations, there are only two cases
when the graph is s-decompositions. If the degree of nodes x, y are both greater than
1, the graph is decomposable only if the neighborhood is obtained by gluing another
block to II. Then we can apply the corresponding replacement as shown in case A. If
the degree of nodes x, y are both 1, the neighborhood is a DCC and can be obtained
either by annihilating xy in IIby gluing a spike, or by gluing {Ia,Ib}.
• If x, y are connected by an edge of weight 4 from y to x, there are two cases. First,
→
the neighborhood can be obtained from gluing an edge − to the graph as in case A.
yx
In this situation, the degrees of nodes x, y are at least 2; Second, the neighborhood
can be obtained from case B. Therefore, to distinguish the above two cases, we first
check the degrees of o. If o has degree greater than 2, o is contained in a neighborhood
as shown in case B. If o has degree 2, we check the degrees of x, y: if the degrees of
both x, y are two, the neighborhood is a disjoint connected component and has two
possible decompositions; if the degrees of both x, y exceed 2, o must be contained in
a neighborhood in A. In latter case, after applying the corresponding replacement, we
keep edge xy and change its weight from 4 to 1.
• If x, y are connected by an edge of weight one from y to x, the neighborhood can only
be obtained from case A.
Next suppose the degree of o is 3. In this case node o can only be contained in a neighborhood shown in B,D1 or D2, otherwise the graph is not s-decomposable. To distinguish
these cases, first we check if the nodes connected to o by an edge of weight 2 are connected
by an edge of weight 4. If so, o must be contained in B. If not, we denote the three nodes
94

connected to o by x, y, z, where y, z are connected to o by edges with weight 2. Note that
x must be connected to o via an edge with weight 1, x, y must be connected via an edge
− with weight 2, degrees of y and z must be 2 otherwise the graph is not s-decomposable.
→
yx
→
Node o is contained in a neighborhood shown as in D1 if o, z are connected via an edge −
oz,
→
D2 if via −
za.
Next suppose the degree of o is 4. In this case node o can only be contained in a
neighborhood shown in one of B, E1-E4, otherwise the graph is non s-decomposable. By
the same argument as in this previous case, we check if o is contained in B. If not, we need
to determine if o is contained in any of E1-E4. Denote the nodes that are connected to
o by edges with weight 1 by y, z, the nodes that are connected to o by edges with weight
2 by x, w. Then y, z must both be connected to one of the nodes that are connected to o.
Assume y, z are both connected to x, then xy, xz both have weight 2. By picture E1-E4,
ow must have weight 2, and the degree of w is 2. By examination of the orientation of the
edges incident to o we determine in with type of neighborhood o is contained.
Finally, if the degree of o is 5, it can be only contained in a neighborhood shown in one of
B, F1-F4, otherwise the graph is non s-decomposable. As above, we check if o is contained
in B. If not, we denote the boundary nodes of o by x, y, z, u, v, where x, y, z are connected to
o by edges of weight 1, u, v are connected to o by edges of weight 2. Note that if the graph is
s-decomposable, one of u, v must be connected to two nodes among x, y, z by edges of weight
2. Assume u is connected to y and w by edges of weight 2. Then, v must be connected to x
by another edge of weight 2, and deg(y) = deg(w) = deg(v) = 2, deg(u) = 3, deg(x) ≥ 2.

95

Table 4.5: m = 1
A1
Decomposition
Degree of p

A2

≥1

≥1

Replacement

4.2.4

n=1

In this case, there is only one edge with weight 2 that is incident to o. Denote the other
endpoint of this edge by p. We consider the number of edges with weight 2 incident to p.
Denote this number by m.
If m = 1, there are two cases, as shown Table. 4.5. We can only attach blocks containing
no edge of weight two to the node p. In both cases, degree of o is one. It is easy to determine
if o is contained in A1 or A2.
If m = 2, there are ten possible cases, as shown in Table 4.6. In either of the cases
A1,A2, we can only attach to o blocks containing no edge of weight 2. Hence after applying
the corresponding replacement, there is no edge with weight 2 that is incident to o. In case
B1 or B2, we can only attach to p blocks containing no edge of weight 2.

96

Table 4.6: m = 2
A1

A2

p

p

2
Decomposition

2

o

2
x

Degree of p

2

o

x

2

2

B1

B2

p

p

Replacement

2

2
Decomposition

4

o

2

2
x

4

o

x

≥2

≥2

C1

Degree of p

C2

Replacement

o

o

2
Decomposition

p
p+

2
2

x

p
p+

2

Degree of p

2

2

Replacement

DCC

DCC

D1

D2

97

x

cont’d

x

x

2
2
Decomposition

o

Degree of p

2

2
2

p+p

y

o

3

2

p+p

y

3

y

y

Replacement
D3

D4

x

x

2
2
Decomposition
Degree of p

o

2

2
2

p+p

y

3

o

2

p+p

y

3

y

y

Replacement
Table 4.6 gives all possible cases with m = 2. To determine the type of neighborhood o
is contained in, let us denote the node connected to o by an edge of weight 2 by p, then
examine the degree of p. According to Table 4.6, if the graph is s-decomposable, deg(p) ≥ 2.
Suppose the degree of p is 2, we denote the other node that is connected to p by x. Note
that the weight of px must be 2. If x is connected to o by an edge with weight 4, then o
must be contained in neighborhood B1 or B2 depending on the orientation of edges. Note
that in this case, the graph is a disjoint connected component. If xo has weight 1, then o
is contained in neighborhood A1 or A2 depending on the orientation of edges. If x is not
connected to o, then the graph must be a disjoint connected component C1 or C2.
Next, suppose the degree of p is 3. By Table 4.6, there are two edges with weight 2
that are incident to p, one of which is op. Denote the other edge of weight 2 by ox (the
98

other endpoint is x). If x is connected to o by an edge of weight 4, then o is contained in
neighborhood B1 or B2. If x is not connected to o, then o lies in neighborhood D1-D4.
Note that in the latter case, the degree of o is 1. If it is neither of the above two situation,
the graph is not s-decomposable.
Finally if the degree of p is greater than 3, o must be contained in neighborhood B1 or
B2.
If m = 3, there are fourteen cases, as shown in Table.4.7.
Table 4.7: m = 3
A1

A2

3

3

B1

B2

Decomposition
Degree of p

Replacement

p
2
Decomposition

p
2

4

p

2

+

2

o

p
2

+

4

2

o

Degree of p

3

3

Replacement

DCC

DCC

B3

p
2
Decomposition
Degree of p

2
4

B4

p
+

p

2
2

o
3

p
2

+

4

o
3

99

2

cont’d
Replacement

DCC

DCC

C1

C2

4

4

C3

C4

4

4

D1

D2

Decomposition
Degree of p

Replacement

Decomposition
Degree of p

Replacement

z
2
2

y

p
2

Decomposition

z

p
+ 2

2

2
4

o

w

p

2

y
x

p
2

+ 2
o

w

Degree of p

5

5

Replacement

DCC

DCC

100

2
4

x

cont’d
D3

z
2
p
2
Decomposition

z

p

2
y

D4

+ 2

2
4

o

w

p

2
2

y
x

p
2

+ 2
o

2
4

x

w

Degree of p

5

5

Replacement

DCC

DCC

Note that the degree of node o in all pictures is 2 except A1 and A2. Therefore, if the
considered node has degree larger than 2, it can only be contained in neighborhood A1 or
A2. In both cases, there are two nodes, denoted by x, y, that are connected to o by edges
of weight 1, and p is connected to both nodes x and y by edges of weight 2. Moreover, the
degree of p is 3, the degrees of x, y are both 2. Suppose o has degree 2, according to Table
4.7, deg(p) = 3, 4 or 5.
First, suppose deg(p) = 3. o can only be contained in a neighborhood shown in B1,B2,B3
or B4. Note that in all these cases, all edges incident to p has weight 2, and the graph is a
disjoint connected component.
Next, suppose deg(p) = 4. Then o can only be contained in neighborhoods of type
C1,C2,C3 or C4. In all these cases, p is incident to four edges of weight 2. Also p is
connected to a node which is also connected to o by an edge of weight 4. Among the
four nodes connected to p, three of them, including o, have degree 2, the remaining node
has degree no less than 2. We can check the orientations of all edges to determine which
neighborhood o is contained in.
Finally, suppose deg(p) = 5. In this case, o can only be contained in neighborhood D1101

D4, and the graph is a disjoint connected component. In all these cases, p is incident to
three edges of weight 2. Denote the other endpoints of these edges besides o by x, y. Node p
is also incident to two edges of weight 1. Denote the other endpoints of these two edges by
z, w. According to Table 4.7, z, w must both be connected to one of x, y by edges of weight
2. Assume it is y. Then o is connected to x by an edge of weight 4. Note that in this case
deg(y) = 3, deg(z) = deg(w) = deg(x) = 2. We can determine which neighborhood o is
contained in by examining the orientations of the edges.

4.3

Summary

In Section 4.2, we exhausted all nodes that are incident to some edges with weight 2. We
also replace a neighborhood of any such node by a consistent one which does not contain
any edge with weight 2. Therefore, for any given weighted graph, we can determine if it is
s-decomposable, and simplify it into a graph containing only edges with weight 1 or 4. Then
we apply the algorithm in [6] to determine if it is block decomposable. Note that every node
is examined at most twice: once in the procedure as in 4.2, once in the algorithm in [6].
Hence the algorithm is linear in the size of the given graph.
Apply the algorithm to Theorem 2.1, we get the following corollary:
Corollary 4.1. Given a skew-symmetrizable matrix B, there exists an algorithm linear in
the size of B to determine if B has finite mutation type.
Proof. Assume the size of B is no less than 3. First, we check if B is mutation-equivalent to
one of the seven exceptional types in Theorem 2.1. If so, B is mutation finite. Since the sizes
of all seven types do not exceed 6, it only takes finite number of operation. If none of the
seven types is mutation equivalent to B, we apply our algorithm to the associated adjacency
102

graph of B. By the previous argument, the number of operation it requires is linear in the
size of B. If the adjacency graph is confirmed to be s-decomposable, B has finite mutation
type.
Remark 4.4. If diagram G is s-decomposable, our algorithm can recover the blocks used to
obtain G since every step of replacement is consistent. In particular, we can determine the
ideal tagged triangulation of bordered surfaces with marked points to each decomposition.
Remark 4.5. A connected diagram G has non-unique decomposition if and only if G is one
of the two diagrams in Figure 4.3.

2

2

2

2
4

Figure 4.3: Diagrams with non-unique s-decompositions

103

Chapter 5
Graphs with Non-unique
Decomposition and Their Associated
Surface
In this chapter we use the algorithms to find the associated surfaces to graphs, diagrams or
matrices with non-unique decompositions.

5.1

Associated Surface to A Decomposition of Diagram

Let B = B(T ) be the signed adjacency matrix of an ideal triangulation T . The gluing
procedure of surface pieces and corresponding decomposition to the associated graph are the
following (see proof of theorem 13.3 in [2]):
• the triangulations of surfaces in Figure 5.1 whose outer sides do not lie on the boundary
of T contribute blocks triangle, diamond and square respectively.
• a triangle with two sides on the boundary does not contribute to the block decomposition, see Figure 2.2.
• a triangle with one side on the boundary contributes a block of spike.
104

1
1

1

2

3

4

2

2

5

4

3

3
Figure 5.1: Triangulation of surfaces
• a punctured-digon with both sides on the boundary yields two disjoint vertices.
• a twice-punctured monogon with the side on the boundary yields a square obtained by
gluing four blocks of spikes, see Figure 5.2.

˜
Figure 5.2: A(2, 2)

Gluing two blocks corresponding to gluing two pieces of triangulations of surfaces: gluing
two white nodes means gluing the corresponding sides of the triangulations, (see Figure. 2.1).
If a decomposition of a block-decomposable graph or s-decomposable diagram G has a
white node, we will glue a triangle surface (first picture in Figure 5.1) to surface T associated
to G, with two sides of the triangle as boundary and the other side glued to the side in T
corresponding to that white node in G, see Figure. 2.2
It is shown in [2] that there is a one-to-one correspondence between s-decomposition
skew-symmetrizable diagrams with fixed decomposition and ideal tagged triangulations of
marked bordered sufaces with fixed tuple of conjugate pairs of edges. Conjugate edges are
two edges inside a digon or a monogon with one of them tagged and the other untagged. We

105

show in next section that most connected graphs with non-unique decomposition correspond
to unique bordered surfaces.

5.2

Results

We list all connected graphs with non-unique decompositions (s-decompositions) in the following tables. They cover all possible situations by the algorithms from [6] and [7]. We
also list all their block decomposition (s-decomposition) and corresponding ideal (tagged)
triangulation of surfaces. The following theorem follows:
Theorem 5.1. If G is a connected block-decomposable or s-decomposable graph, then G is
either associated to a unique bordered surface , or isomorphic to the diagram in graph 5, 11
or 12.

106

Table 5.1: Graph 1

Graph 1
1
1

2

1

2

+

2
o

Decomposition

4

3
2

3
+

o
+o
3

3

4

4

o

o
1

2
3

4

4

o

2
Surfaces
Type

Disk

Disk

107

3

1

Table 5.2: Graph 2

Graph 2

p

1
1 1

2 2

Decomposition

p

3 4

o

3 4
4

3
p

3 4
1

1
3

o
2

p

3

2
4

Surfaces
Type

2

2

o

o
o

p

1

4

p

o
Sphere

Sphere

108

Table 5.3: Graph 3

Graph 3
1

o
Decomposition

2

2

1

4

+o

1

2

o o

4 4

4
3

3

1

4

4
2
3

1

3

2
o

o
Surfaces
Type

3

Disk

Disk

109

Table 5.4: Graph 4

Graph 4
1
1 1

1
2

4
2

2

4

4

2

5

4
Decomposition

5

3

5

3

1

3
4

2

1

3
Surfaces
Type

5

3

3

5
2

2
2

4
4

5

Disk

Disk

110

1
4

2

3

5
Disk

4

Table 5.5: Graph 5

Graph 5
1

1

4
+

4

Decomposition

4
4

2

2
2

3
2

3
1
2

4

1
2

4
3

3
Surfaces
Type

Disk

Annulus

111

Table 5.6: Graph 6
1

2

p

o

Graph 6

4

3

1

2

2

1

2
p

o p

p
Decomposition

o

4

p
3

p

o

o

o
o

4

4

3

p
4

2

4

2

o

o
4

2
3

3
Surfaces
Type

1

Sphere

Sphere

112

o

+p

p
3

p

1

1

1
3
Sphere

Table 5.7: Graph 7

Graph 7
1

2
1
o
+
o

Decomposition

o +o
3

4

4

3

1

o
2

Surfaces
Type

3

4

1

3
1

3
o

4

Disk

Disk

113

o

+

o

4

2

3
o

21

2

2
4

Disk

Table 5.8: Graph 7’

Graph 7’
1

2
1

1
o
+
o
Decomposition

2
o

+
3

4

4

+

o

o

4

3

4
Surfaces
Type

1

2

2

+
3

4

o

1 1
+

o

3

2
o

4

3
Disk

114

+
3

4

o
2

Disk

2

+

1
3

2

4

1
Disk

3

Table 5.9: Graph 8

Graph 8
1

1
1

1

Decomposition

1

+

2

34

4

3

3
+

o
+o
3

2

+

o o

4

o

4

2

1

o
+

2

3

4
1
o

1
2

3

4

3

1

4

o

4

3

2

2
o

Surfaces
Type

Disk

Disk

115

Disk

Table 5.10: Graph 9

Graph 9
1

1
4

+

1

4 4

2

1
2 2

2 2

4 4

+
Decomposition

3

3

3

3

1
1
3

1

4

2

4

2

2

3

3
3

Surfaces
Type

Disk

Disk

116

Disk

Table 5.11: Graph 10

Graph 10
1

1 1

1
2
2

4
4

4
4

3 3

Decomposition

2
2

3

3

3

1

1
4
2

3

Surfaces
Type

2

4

1
4

1

2
3

Disk

Disk

117

2

4
3

Disk

Table 5.12: Graph 11

Graph 11
2

2

Decomposition

3

1

1

2

3

1

2
1

3
1

3

2
Surfaces
Type

Disk

Disk

118

3

Table 5.13: Graph 12

Graph 12
3
3

1
1

1
2

Decomposition

2

2
o
o

1
2
1
Surfaces
Type

Disk

Disk

119

Table 5.14: Graph 13

Graph 13
3

3

3
o o
Decomposition

o
o

1

2

2

o
2

2

o
1

3
Surfaces
Type

1

2

o
1

o
o

1

1

3

2

3

Disk

Disk

120

Disk

Table 5.15: Graph 14

Graph 14
3

3
3
o

3
o o
Decomposition

1

2

1

o
o

1

o

1

2
2

2

1

1

o

3

o
2

3

3
Surfaces
Type

1

2

o
2

1

Disk

Disk

121

Disk

Table 5.16: Graph 15
4

1
o

Graph 15

2

3

4

1

1

4

o o
o

3

2

3

2

o

2

3

2
2

4

1
o

2

1
Surfaces
Type

1

3

o
3

o
o

3

2

3
Decomposition

1

4

1

4
4

4

Disk

4

1

Disk

122

3

2

Disk

The following diagrams are s-decomposable and have non-unique decompositions. Both
of them are associated to unique surfaces.:
Table 5.17: Graph 16
2

2

Graph 16
o
Decomposition

o

o

2
a

2
b

2

2

a
a

b
b

o
a
a1
a2
Surfaces
Type

b

b1
b2

Disk

o1 o2

Disk

123

Table 5.18: Graph 17
2

2
4

Graph 17

o

o
Decomposition

2

2

2
4

a

b

o

2

a
a

b
b
a

b
o1 o2

b2
b1
Surfaces
Type

a1
a2
Disk

Disk

124

BIBLIOGRAPHY

125

BIBLIOGRAPHY
[1] Sergey Fomin, Michael Shapiro, and Dylan Thurston. Cluster algebras and triangulated
surfaces. part i: Cluster complexes. Acta Math. 201 (2008), 83-46.
[2] Anna Felikson, Michael Shapiro, and Pavel Tumarkin. Cluster algebras of finite mutation
type via unfoldings. To be published in JEMS.
[3] Gregg Musiker and Christian Stump. A compendium on the cluster algebra and quiver
package in sage. S´m. Lothar. Combin. 67 (2011).
e
[4] Anna Felikson, Michael Shapiro, and Pavel Tumarkin. Skew-symmetric cluster algebras
of finite mutation type. Int Math Res Notices, 2012.
[5] George Lusztig. Introduction to quantum groups. Progr. Math. Vol. 110, Birkhauser,
Boston, 1993.
[6] Weiwen Gu. Decomposition algorithm for median graph of triangulation of a bordered
2d surface. Electronic Journal of Combinatorics.
[7] Weiwen Gu. The decomposition algorithm of skew-symmetrizable exchange matrices.

126