Advances in Pure Mathematics, 2012, 2, 119-123 Published Online March 2012 (
Homology Curve Complex
Ningthoujam Jiban Singh1*, Himadri Kumar Mukerjee2
1Department of Mathematics, Assam University, Silchar, India
2Department of Mathematics, North-Eastern Hill University, NEHU Campus, Shillong, India
Email: {njiban, himadrinehu}
Received October 22, 2011; revised November 1, 2011; accepted November 12, 2011
A homological analogue of curve complex of a closed connected orientable surface is developed and studied. The dis-
tance in this complex is shown to be quite computable and an algorithm given (Theorem 3.5). As an application of this
complex it is shown that for a closed orientable 3-manifold, and any of its Heegaard splittings, one can give an algo-
rithm to decide whether the manifold contains a 2-sided, non-separating, closed incompressible surface (Theorem 1.1).
Keywords: Homology Curve Complex; Heegaard Splittings; Incompressible Surface
1. Introduction
Jaco and Oertel ([1]) gave an algorithm to decide if a
3-manifold is a Haken manifold. Their algorithm is an
offshoot of an algorithm given by Haken himself. Haken
has developed in 1960’s ([2]) an algorithm to decide if a
fundamental normal surface of a given presentation of a
compact irreducible 3-manifold is injective. Any normal
surface can be constructed from these fundamental nor-
mal surfaces and if the input is a normal surface then by
successive application of the above algorithm one can
check if the normal surface is injective. But one does not
know for how many normal surfaces (finite or infinite)
this algorithm has to be run. Jaco and Oertel ([1]) pro-
duced a finite collection of constructible normal surfaces
(test surfaces) only on which this algorithm has to be run.
Results of similar flavour has been found by Jaco, Let-
scher, and Rubinstein [3] and many others.
We, on the other hand, give here an algorithm whose
input is any Heegaard splitting of the given manifold. We
develop a homological version of curve complex, which
we call “homology curve complex”.
The term homology curve complex used in this paper
is inspired by the term used in the set of open problems
posed by Joan Birman in the arXiv preprint [4], page no.
8, line 12, but is different from what she meant there.
This term has also been used recently by Ingrid Irmer in
his arXiv preprint [5] with a different meaning.
We prove that for surfaces of genus greater than one,
this complex is connected (3.3), hence a notion of dis-
tance between vertices, which we call “H-distance” can
be defined. We give an algorithm which returns H-dis-
tance of two given vertices, theorem (3.5). Using this
complex we define an analogue of the Hempel distance
of a Heegaard splitting of a 3-manifold. This distance is
then used to decide if the manifold contains a closed,
two-sided incompressible surface or not, a homological
analogue of Johnson and Patel ([6], lemma 4), which also
extends to genus 2 in our case. Finally an algorithm is
given which takes as its input a Heegaard splitting of a
given closed connected orientable 3-manifold and decides
if this distance is zero or not in polynomial time.
Every closed connected orientable 3-dimensional mani-
fold M admits a Heegaard splitting, i.e. , a decomposition
into two orientable handlebodies V and V which meet
along their boundary. This common boundary is called a
Heegaard surface. Alternately, we may view M as ob-
tained from the two handlebodies by identifying their
boundaries under a homeomorphism f : V V. Hee-
gaard splittings are a convenient way to define a 3-
manifold, but a priori it is difficult to get structural in-
formation about the manifold from them. It is in this light
the following result assumes importance.
(Theorem 4.1) Given a closed, connected, orientable 3-
manifold M and a Heegaard splitting g
genus g > 1, there is an algorithm, which runs in poly-
nomial time, to decide whether M contains a nonsepa-
rating, 2-sided, closed incompressible surface.
In Section 2 we give a brief recollection of complex of
curves and some related concepts. We introduce in Sec-
tion 3 an analogue of curve complex, “homology curve
complex”, associated with the surface and a notion
of distance, “H-distance”, and prove several results de-
*The first author acknowledges CSIR, India, for financial supports under
grant F. No. 9/347(159)/2k3-EMRI dated 13.09.2003.
opyright © 2012 SciRes. APM
scribing their properties including a result giving an al-
gorithm to compute the H-distance between a pair of ver-
tices: see lemma (3.2), lemma (3.3), theorem (3.5), pro-
position (3.6), proposition (3.7). Section 4 starts with the
introduction of the notion of an analogue of the Hempel
distance of a Heegaard splitting followed by a recollec-
tion of complete meridian systems and some results re-
lated to these. Finally, we complete the proof of theorem
(1.1) giving an algorithm which takes as its input a Hee-
gaard splitting of the given 3-manifold and decide in po-
lynomial time if the manifold contains a nonseparating,
2-sided, closed, incompressible surface.
2. Preliminaries
For standard 3-manifold terminologies, we refer the reader
to Jaco [7]. The curve complex C() for a compact, con-
nected, closed, orientable surface is the abstract sim-
plicial complex whose vertices are isotopy classes of
essential, simple closed curves in and whose sim-
plices correspond to sets of distinct isotopy classes which
are represented by pairwise disjoint circles (simple closed
curves) in . If C() is connected we can define an
integer valued distance d(x, y) between a pair of vertices
x, y as the number of edges in the shortest edge path be-
tween them. Given a handlebody V and a homeomor-
phism f: V, the handlebody set (or a disk complex)
is the set of (isotopy classes of) circles in
bound properly embedded essential discs in V. The genus
g boundary set
is the set of non-separating circles
in such that each bounds a properly embedded,
2-sided, incompressible, genus g surface in V and the
boundary set is the union
=g 0
. The Hempel
distance, denoted by d(V, V), of the Heegaard splitting
(V, V;
) as defined in Hempel [8] is given by d(V, V)
= inf{d(x, y): x is a vertex of , y is a vertex of
The boundary distance as defined in Johnson and Patel
[6] is given by
 .
3. Homology Curve Complex
denote a closed, connected and oriented surface
of genus g > 1. It is well-known that H1(
;) has the
standard bilinear intersection form ,, which is sym-
plectic (i.e., x, x = 0, x H1(
;) and the form
establishes a self-duality on H1(
;) (i.e. an isomor-
phism H1(
;) H1(Hom
 ;), )), see for
example Johnson [9]. For x, y H1(
;), the integer
x, y is called the algebraic intersection number between
x and y. A basis of H1(
;)) (which is a free -
module of rank 2g) is called canonical or symplectic if it
is of the form {a1, ···, ag, b1, ···, bg} with ai, aj = bi,bj
= 0, and ai, bj =
ij (Kronecker delta), i, j {1, 2, ···,
g}. It is well-known that H1(
;) has the standard
canonical basis (see Figure 1).
A nontrivial element x H1(
;) is said to be
primitive (relative to the canonical basis) if its coordi-
nates are relatively prime.
3.1. Definition
We define the homology curve complex of the surface
, denoted by HC(
), to be an abstract simplicial
complex whose vertices are the primitive elements of
;) and a collection {c1, ···, cm} of m distinct
vertices form an (m 1)-simplex if the algebraic inter-
section numbers ci, cj = 0, i, j {1, ···, m}. In the
following, we shall represent a vertex of HC(
) by its
coordinates relative to the standard canonical (ordered)
basis B.
3.2. Lemma
For g > 1, if x, y are distinct vertices of HC(
), then
there is a vertex z of HC(
) such that x, z = 0 = y, z.
Proof. The standard intersection form , on H1(
induces a module homomorphism f: H1(
 
;) ×
defined by t (
t, x, t, y). Since is a PID, ker(f)
and im(f) are free submodules of the free -modules
;) and × respectively and the sequence
0 ker(f) H1(
;) im(f) 0 is split-exact. So,
;) = ker(f) im(f). Since di (ker(f)) =
;) (im(f)) 2g 2 2, we get a
nontrivial element z H1(
;) satisfying x, z = 0 =
y, z and so by dividing each of the co-ordinates of z by
their gcd, if necessary, we can always take z to be a
primitive element.
3.3. Lemma
For g > 1, HC(
) is an infinite dimensional, connected
abstract simplicial complex and if the integer valued
distance dH(x, y) between a pair of vertices x, y is the
number of edges in the shortest edge path between them,
then dH is explicitly given by
0, if ;
1, if and ,0;
2, otherwise
xdxy yyx
 
Proof. It is easy to see that m , the set Am = {(1,
x, 0, ···, 0) 2g: 1 x m, x } of vertices of
) forms an (m 1)-simplex in HC(
). There-
Figure 1. A representative of a canonical basis for H1(g;).
Copyright © 2012 SciRes. APM
N. J. SINGH ET AL. 121
) is infinite dimensional. To see that HC(
) is
connected, let x, y be distinct vertices of HC(
If x, y = 0, then they can be joined by an edge by
definition; otherwise by lemma (3.2), there is a vertex z
such that x can be joined to z by an edge and then z can
be joined to y by another edge.
Notice that a circle α on
is separating if and only
if its homology class is zero. There is a characterization
of the vertex set of HC(
3.4. Lemma
(Meyerson [10]) A nontrivial element of H1(
;) can
be represented by a non-separating circle on
if and
only if it is primitive relative to the standard canonical
(ordered) basis of H1(
; ).
3.5. Theorem
For g > 1, there is an explicit algorithm which takes as
, a canonical ordered basis B = {a1, ···, ag,
b1, ···, bg} for the homology H1(
;), a pair of verti-
ces α, β of HC(
) and returns the distance between
Proof. By part (f) of Theorem 1 in [11], there is an al-
gorithm to compute the algebraic intersection number
α, β and also the co-ordinates of α and β relative to the
basis B in polynomial time. If α = β then by lemma 3.3
dH(α, β) = 0. If α β by lemma 3.3 again, dH(α, β) = 1 if
and only if the algebraic intersection number between α
and β = 0. If neither of these hold, then by lemma 3.3
again dH(α, β) = 2.
3.6. Proposition
With the same notations as above, every simplicial auto-
: HC(
) HC(
) induces an isometry
on the metric space (HC0(
), dH), where HC0(
) de-
notes the set of vertices of HC(
Proof. Let x, y be vertices of HC(
) with dH(x, y) =
k, where k = 0, 1, or 2. For k = 0, 1, the result follows
from the fact that a simplicial automorphism maps m-
simplices to m-simplices and in particular if x y and
x, y = 0, thereby dH(x, y) = 1, then x, y form an edge. So,
λ(x) λ(y) will also form an edge, so λ(x), λ(y) = 0
thereby dH(λ(x), λ(y)) = 1. If k = 2, i.e. if x, y 0, by
lemma (3.2) there is a vertex z of HC(
) such that
x, z = 0 = y, z. So, λ(x), λ(z) = 0 = λ(y), λ(z). This
gives, by triangle inequality, dH(λ(x), λ(y)) 2. However,
dH(λ(x), λ(y)) < 2 implies that dH(λ(x), λ(y)) = 0 or 1. This
implies that λ(x), λ(y) = 0 and so x, y = 0, which is a
contradiction. So, dH(λ(x), λ(y)) = 2.
3.7. Proposition
Let k {0, 1, 2}. For g > 1, the set {( x, y) HC0(
) ×
)|dH(x, y) = k} is infinite.
Proof. For k = 0, 1, the result follows from lemma
(3.3). For k = 2, there are vertices a, b in the vertex set of
) with algebraic intersection number 1, which
also have respective representative circles with geometric
intersection number 1. Consider the positive Dehn twist
Ta. Now, n , a(b), b = b + na, ba, b =
na, ba, b + b, b = n and so by definition,
dH(T (b), b) = 2, whenever n 0. This proves the result.
4. Applications
As an application of the concepts developed in the pre-
vious sections we shall present a complexity measure for
Heegaard splitting using the homology curve complex
and prove.
4.1. Theorem
(Theorem 1.1) Given a closed, connected, orientable 3-
manifold M and a Heegaard splitting g
 of
genus g > 1, there is an algorithm, which runs in polyno-
mial time, to decide whether M contains a non-sepa-
rating, 2-sided, closed incompressible surface.
Before giving the proof we need to introduce some
more notations and definitions:
4.2. Definition
For a Heegaard splitting (V, V;
), let D (resp. D)
denote the set of vertices in HC(
), each represented
by a circle whose homology class is nontrivial in
but trivial in V (resp. V). Then, we define the H-distance,
denoted by dH(V, V), for the splitting (V, V;
) to be
the inf{dH(x, y): x D, y D}.
As immediate consequence of lemma (3.3), we have
the following.
4.3. Lemma
For (g > 1), the H-distance of the Heegaard splitting
takes only the finite values 0, 1 or 2.
4.4. Remark
For any Heegaard splitting g
of genus 3 or
greater, Johnson and Patel [6] showed, using complex of
curves (different from homology curve complex), an
analogous result that distance d(
) is equal to 0, 1 or
4.5. Definition
A complete meridian system (or simply cms) for a han-
dlebody V is a set L = {D1, ···, Dg} of pairwise disjoint
properly embedded discs on V such that the manifold
obtained by cutting V open along L is a 3-ball. The
Copyright © 2012 SciRes. APM
boundaries of the discs of a cms for V form a meridian
system for the surface V.
Given a cms L = {D1, ···, Dg} for a handlebody V, let α
be a simple arc on the boundary V connecting Di and
Dj (i j) with int (α) disjoint from L. Let N denote a
regular neighbourhood of Di Dj α in
. Then,
N has three components, one is a copy of Di, one is a
copy of Dj and the other one is called a band sum of Di
and Dj along α on V which gives arise to a compress-
ing disc Dij in V (after slight pushing the interior of the
disc inside V) with boundary Dij being the band sum.
Denote L = {D1, ···, Di1, Dij, Di+1, ···, Dg}. We say that
L is obtained from L by an elementary slide (and Dij is
also called a disc slide). If a cms L on V is obtained from
a cms L on V via a finite number of elementary slides and
isotopies, we say that L and L are equivalent and denoted
by L L. We also say that L slides to L. The following
fact about cmss of discs on a handlebody V is well-
known (see for example [12]), which tells us how two
cmss of discs for a handlebdy are related.
4.6. Proposition
Assume that L is a cms of discs for a handlebody V and L
slides to L, then L is also a cms of discs for V. Con-
versely, any two cmss of discs for V are equivalent.
4.7. Remark
It is well-known that if D is a non-separating properly
embedded compressing disc for a genus g handlebody V,
then {D} can be extended algorithmically to a cms of
discs for V in g many steps.
Proof of the theorem (4.1). We will begin with the
following characterization of a closed connected orien-
table 3-manifold which is an extension of Johnson-Patel
([6], lemma 4) to the setting of homology curve complex.
4.8. Theorem
Let M be a closed connected orientable 3-manifold with
a Heegaard splitting (V, V;
) of genus g > 1. Then
for any pair of cmss L = {D1, ···, Dg}, L = {1
, ···,
for the respective handlebodies V and V, the following
statements are equivalent:
1) M contains a non-separating, two-sided, closed in-
compressible surface;
2) H1(M) is infinite;
3) The matrix A = (aij), where aij is the algebraic in-
tersection number of Di and
, is singular;
4) d(
 
) = 0;
5) dH(V, V) = 0.
Proof. 1 2 is a classical result (see Jaco [7], or
Johnson-Patel [6]). 2 3 4 is due to Johnson-
Patel ([6], lemma 4). By definition D is a quotient of
, consisting of homology classes of elements of ,
so d(
) = 0 implies dH(V, V) = 0, or 4 5. Now
we prove that 5 1. If
dH(V, V) = 0 then there exists x
). Pick two disjoint simple closed
curves and on
, each of which represents x. Then,
and bound two-sided, non-separating properly em-
bedded compact surfaces F V and F V respectively.
Since and are homologous in
, they cobound a
compact subsurface S of
. The union F S F is
a two-sided, non-separating closed surface embedded in
M. By compressing repeatedly, if necessary, we eventu-
ally find a closed, non-separating, two-sided incompre-
ssible surface in M.
We are ready to complete the proof of theorem (4.1).
Proof. (Completion of proof of theorem (4.1))
By theorem (4.8), existence of a non-separating, two-
sided, closed incompressible surface in M is reduced to
examining if dH(V, V) = dH(D, D) = d(
) = 0, which
in turn reduced to examining if the matrix A = (aij) is
singular, where aij is the algebraic intersection number of
Di and Dj. One can compute the entries aij of the matrix
A in polynomial time (see for example [11] theorem 1 (f))
and the non-singularity of a matrix can be determined in
polynomial time (see for example section 2.3 of [13]).
This completes the proof of the theorem (4.1).
4.9. Problem
It will be interesting to characterize those closed ori-
entable 3-manifolds which possess Heegaard splittings
having H-distance 1 and/or 2.
5. Acknowledgements
We acknowledge Prof. Joan Birman for her useful com-
ments on an earlier version of the draft of our paper. We
also acknowledge the anonymous referees for their useful
[1] W. Jaco and U. Oertel, “An Algorithm to Decide If a 3-
Manifold Is a Haken Manifold,” Topology, Vol. 23, No. 2,
1984, pp. 195-209. doi:10.1016/0040-9383(84)90039-9
[2] W. Haken, “Theorie der Normalflachen,” Acta Mathe-
matica, Vol. 105, No. 3-4, 1961, pp. 245-375.
[3] W. Jaco, D. Letscher and J. H. Rubinstein, “Algorithms
for Essential Surfaces in 3-Manifolds,” Contemporary
Mathematics, Vol. 314, 2002, pp. 107-124.
[4] J. Birman, “The Topology of 3-Manifolds, Heegaard Dis-
tances and the Mapping Class Group of a 2-Manifold,”, 2005.
Copyright © 2012 SciRes. APM
Copyright © 2012 SciRes. APM
[5] I. Irmer, “Geometry of the Homology Curve Complex,”, 2011.
[6] J. Johnson and T. Patel, “Generalized Handlebody Sets
and Non-Haken 3-Manifolds,” Pacific Journal of Mathe-
matics, Vol. 235, No. 1, 2005, pp. 35-41.
[7] W. Jaco, “Lectures on Three-Manifold Topology,” CBMS
Regional Conference Series in Mathematics, American
Mathematical Society, Providence, 1980.
[8] J. Hempel, “3-Manifolds as Viewed from the Curve Com-
plex,” Topology, Vol. 40, No. 3, 2001, pp. 631-657.
[9] D. Johnson, “An Abelian Quotient of the Mapping Class
Group Ig,” Mathematische Annalen, Vol. 249, No. 3, 1980,
pp. 225-242. doi:10.1007/BF01363897
[10] M. D. Meyerson, “Representing Homology Classes of
Closed Orientable Surfaces,” Proceedings of AMS, Vol.
61, No. 1, 1976, pp. 181-182.
[11] M. Schaefer, E. Sedgwick and D. Stefankovic, “Algori-
thms for Normal Curves and Surfaces,” Lecture Notes in
Computer Science, Springer, 2002, New York, pp. 370-
[12] F. C. Lei, “Complete Systems of Surfaces in 3-Mani-
folds,” Mathematical Proceedings of the Cambridge Phi-
losophical Society, Vol. 122, No. 1, 1997, pp. 185-191.
[13] D. Saunders and Z. D. Wan, “Smith Normal Form of
Dense Integer Matrices, Fast Algorithms into Practice,”
Proceedings of the 2004 International Symposium on Sym-
bolic and Algebraic Computation, 4-7 July 2004, San-