Computer recognition of Seifert 3-manifolds

Sergei V. Matveev^{1}

Let M be a 3-manifold about which we suspect that it is Seifert. How can we determine its name, i.e., its base surface and nonnormalized Seifert invariants of a few distinguished fibers such that all exceptional fibers are included? Of course, one can try a “brute force” algorithm which, for example, lists all triangulations of M and compares them step by step with all triangulations of all Seifert manifolds. But such algorithms are, as a rule, more than exponential and hence impractical. The same relates to any algorithm based on the Haken method of normal surfaces. Therefore, there are no chances to realize such algorithms by computer programs, at least in the visible future. On the other hand, experienced topologists recognize 3-manifolds rather quickly. Consciously or intuitively, they use other algorithms, which are much more efficient. However, one should pay for that. The price is that we allow an algorithm to be only partial (i.e., not an algorithm at all in the formal meaning of this expression).

We describe here a partial recognition algorithm of Seifert manifolds, which, as preliminary computer experiments show, is fairly efficient. We begin with a description how one can present 3-manifolds in the computer memory and how one can manipulate with them.

1 Computer Presentation of 3-Manifolds

What we need now is an economic way of presenting 3-manifolds in a form that computer would understand. The idea consists in replacing 3-manifolds by cell complexes (their spines) and encoding the spines by strings of integers.

1.1 Cell Complexes

In topology of manifolds the notion of a cell complex is usually considered in a more general sense than in computer topology(see [8, 9]). So we briefly recall it, restricting ourselves to the 2-dimensional case. We prefer an inductive definition.

1. A 0-dimensional cell complex X^{0} is a finite collection of points called vertices.

2. A 1-dimensional cell complex X^{1} is obtained from a 0-dimensional complex X^{0} by attaching several 1-dimensional cells (i.e., arcs). The endpoints of the arcs are attached to the vertices of X^{0}, and the arcs must have no other common points. In other words, a 1-dimensional cell complex is nothing more than a graph (loops and multiple edges are allowed).

1Chelyabinsk State University and Max-Planck-Institute für Mathematik (Bonn). The author is partially supported by grants E00-1.0-2.11, RFBR-02-01-01-013, and UR.04.01.033.

Figure 1: Returns inside edges are forbidden

Figure 2: Two complexes with the same incidence relation

3. A 2-dimensional cell complex X^{2} is obtained from a 1-dimensional complex X^{1} by attaching several 2-dimensional cells. In other words, we take a collection {D_{1}, …, D_{n}} of disjoint 2-dimensional discs and attach each disc D_{i} to X^{1} via an attaching map φ_{i}: ∂D_{i} → X^{1}. It is convenient to assume that the inverse image φ^{−1}(e) of each open 1-cell e of X^{1} consists of open connected subarcs of ∂D_{i} such that each of them is mapped onto e homeomorphically. In other words, we require that the boundary curve l_{i} = φ_{i}(∂D_{i}) of every 2-cell pass along the edges monotonically, without returns inside them. For example, the situation shown in Fig. 1 is forbidden. X^{1} is called the 1-dimensional skeleton of X^{2}.

In general, the incidence relation between cells does not determine X^{2}. It is necessary to know in which direction the boundary curve of each 2-cell l passes along each edge as well as the cyclic order in which l_{i} passes along different edges. For example, consider two cell complexes obtained from a rectangle by identifying its vertices to one point and by different identifications of the sides (see Fig. 2). Each of them has one vertex, two loop edges, and one 2-cell attached to each edge exactly twice. Nevertheless, the complexes are different, since one of them is a torus while the other is a 2-sphere with three identified points.

On the other hand, information on the graph X^{1}, the orientations of edges, and the order in which the boundary curves of the 2-cells of X^{2} pass along the oriented edges is quite sufficient for reconstructing X^{2}. The corresponding data can be expressed numerically as follows. First, we number the vertices and the edges, and write down all the edges as a sequence of pairs (i_{1}, j_{1}), …, (i_{m}, j_{m}). Here are the numbers assigned to the vertices joined by the k-th edge. Simultaneously, we orient each edge (i_{k}, j_{k}) by an arrow directed from the vertex i_{k} to the vertex j_{k}. Second, for each 2-cell we write down a string (p_{1} p_{2} … p_{n}) of non-zero integers (± edges’ numbers) which show how the boundary curve of the 2-cell passes along edges. The signs of p_{i} show the directions in which the curve passes along the edges. For example, the complexes in Fig. 2 can be described by the following data:

1. Edges: (1, 1), (1, 1) (in both cases);

2. 2-Cells: (1 2 − 1 − 2) in the first case and (1 − 1 2 − 2) in the second.

Obviously, the total number of vertices, the sequence of pairs, and the collection of strings determine X^{2}. It is less obvious that if the link of each vertex is connected (i.e., if each vertex of X^{2} has a cone neighborhood with a connected base), then X^{2} is completely determined by the strings only. Indeed, to recover X^{2}, it suffices to do the following:

1. Realize the strings by boundaries of disjoint polygons with oriented and numbered edges;

2. Identify the edges that have the same numbers via orientation preserving homeomorphisms.

Then the 2-dimensional cell complex thus obtained is homeomorphic to X^{2}.

We do not describe any specific realization of the above data in the computer memory. One can use arrays of integers; when an object-oriented programming language is used, the concepts of the cell complex, the spine, and others lend themselves to be used as classes. In that case, this section serves towards developing these classes; indeed, in the upcoming sections we describe the main algorithms we will apply to spines, and this description will help us to determine which methods should be incorporated into that class, as well as which operations would be applied to its objects.

1.2 Special Spines

A convenient method of computer presentation of 3-manifolds consists in replacing them by their special spines.

Definition 1.1 Let M be a compact connected 3-dimensional manifold with boundary. A subpolyhedron P ⊂ IntM is called a spine of M if M ↘ P, that is, M collapses to P. By a spine of a closed connected 3-manifold M we mean a spine of M \ IntB^{3} where B^{3} is a 3-ball in M. By a spine of a disconnected 3-manifold we mean the union of spines of its connected components.

Figure 3: Allowable neighborhoods in a simple polyhedron

Definition 1.2 A compact polyhedron P is called simple, if the link of each point x ∈ P is homeomorphic to one of the following 1-dimensional polyhedra:

(a) a circle (then x is called nonsingular);

(b) a circle with a diameter (then x is a triple point);

(c) a circle with three radii (then x is a true vertex).

Typical neighborhoods of points of a simple polyhedron are shown in Fig. 3. Let us describe the structure of simple polyhedra in detail. Each simple polyhedron is naturally stratified. In this stratification each stratum of dimension 2 (a 2-component) is a connected component of the set of nonsingular points. Strata of dimension 1 consist of open or closed triple lines, and dimension 0 strata are true vertices. Sometimes it is convenient to imagine true vertices as transverse intersection points of triple lines.

It is natural to request each such stratum to be a cell, that is, we would like P to be cellular. We will make this a demand of our future considerations, as can be seen in the following definition:

Definition 1.3 A simple polyhedron P is called special if

1. Each 1-stratum of P is an open 1-cell;

2. Each 2-component of P is an open 2-cell.

Theorem 1.4 [2, 10] If two compact connected 3-manifolds have homeomorphic special spines and either both are closed or both have nonempty boundaries, then these 3-manifolds are homeomorphic.

The meaning of the above theorem is that any special spine of a manifold determines it uniquely. It follows that special spines may be viewed as presentations of 3-manifolds.

However, it is convenient to widen the class of special polyhedra by considering a class of what we call almost simple polyhedra. Roughly speaking, the class of almost simple polyhedra is the minimal class which contains special polyhedra and is closed with respect to the passage to subpolyhedra.

Definition 1.5 A compact polyhedron P is said to be almost simple if the link of any of its points can be embedded into Γ_{4}, a complete graph with four vertices.

It is convenient to present Γ_{4} as a circle with three radii. One usually considers only almost simple polyhedra that cannot be collapsed onto smaller subpolyhedra. It is easy to see that any proper subpolyhedron of the circle with three radii can be collapsed onto a polyhedron L having one of the following types:

(a) L is either empty or a finite set of n ≥ 2 points;

(b) L is the union of a finite (possibly empty) set and a circle;

(c) L is the union of a finite (possibly empty) set and a circle with a diameter;

(d) L is Γ_{4}.

The “can’t start” property assures us that an almost simple polyhedron P cannot be collapsed onto a smaller subpolyhedron if and only if the link L of any point of P is contained in the above list.

For example, a wedge of any simple polyhedron and any graph without free vertices satisfies this condition and hence cannot be collapsed onto a smaller subpolyhedron. This example is very typical, since any almost simple polyhedron P can be presented as the union of its 2-dimensional and its 1-dimensional parts. The 1-dimensional part (the closure of the set of points with 0-dimensional links) is a graph, the 2-dimensional part consists of points whose links contain an arc. If P cannot be collapsed onto a smaller subpolyhedron, then its 2-dimensional part is a simple polyhedron (maybe disconnected).

1.3 3-Manifolds as Thickened Spines

Recall that by Theorem 1.4, any 3-manifold is determined by its special spine. Therefore, numerical representation of cell complexes is sufficient for presenting 3-manifolds: we simply use representation of their special spines. However, while manipulating with manifolds, it is convenient to have more freedom by allowing spines which are not special (almost simple would be more than enough). The problem is that an almost simple and even simple spine does not determine the manifold.

For example, direct and twisted I-bundles over a closed surface F are not homeomorphic, but have the same simple spine (a copy of F). In this example one of the manifolds is orientable, while the other is not. An example of closed orientable 3-manifolds having homeomorphic almost simple spines can be obtained by considering connected sums M_{1}#M_{2} and M_{1}#(−M_{2}), where M_{1}, M_{2} are oriented. If neither M_{1} nor M_{2} admit an orientation reversing involution, then M_{1}#M_{2} and M_{1}#(−M_{2}) are distinct, although they have homeomorphic almost simple spines obtained from simple spines of M_{1}, M_{2} by joining them by an arc. Finally, an example of two orientable 3-manifolds with boundary having the same simple spine is shown in Fig. 4. The direct products of a punctured torus T_{0}^{2} and a twice punctured disc N^{2} by S^{1} are distinct, but have the same simple spine Θ × S^{1}, where Θ is a theta-curve.

Figure 4: T_{0}^{2} ×S^{1} and N^{2} ×S^{1} are not homeomorphic, but have the same simple spine Θ × S^{1}

It is clear now that an almost simple spine P of a 3-manifold M determines M only if we supply P with additional information. Let us describe an example of what information that should be, for the case when P is simple. We assume that P is decomposed into cells, i.e., is presented as a cell complex. Since P ⊂ IntM, each 2-cell of P has two sides. It is easy to show that P determines M, if we know how these sides are glued together in a neighborhood of each edge of P. This information can be written into a matrix which encodes the gluing of the sides.

However, this approach does not seem very natural. We are forced to decode the information written into the matrix each time we need it, and then to encode it again. On the other hand, the sides of 2-cells have a very clear geometric interpretation, which can be used for specifying the thickening. Let us identify M with a close regular neighborhood of P. There is a natural retraction M → P such that its restriction p: ∂M → P possesses the following properties:

1. The inverse image p^{−1}(C) of every open k-dimensional cell C of P consists of two open 2-cells if k = 2, three open arcs if k = 1, and four points if k = 0.

2. The restriction of p onto each of these 2-cells and arcs is a homeomorphism onto the corresponding 2-cell or edge of P.

The 2-cells, arcs and points in ∂M described above form a cell decomposition of ∂M. So the sides of 2-cells of P are nothing more than the 2-cells of ∂M. Under the name “DS-diagrams” such decompositions had been introduced and investigated by H. Ikeda and Y. Inoue [6].

Let us consider now almost simple spines containing no points with disconnected links, in particular, no 1-dimensional part. They too determine DSdiagrams on ∂M. The only difference is that each free (i.e., having valence 1) edge of P has only one counterpart in ∂M, see Fig. 5.

It is evident that P and ∂M, represented by cell complexes as described above (together with the correspondence relation between cells of ∂M and P induced by p: ∂M → P), determine M in a unique way.

The case when P contains a 1-dimensional part is slightly more complicated. The same relates to all almost simple spines having points with disconnected

Figure 5: The behavior of a DS-diagram near ∂P

links, like the cone over two or three disjoint segments. The problem is that we lose the correspondence between cells of ∂M and P. For example, if e is a principal edge, i.e., an edge of the 1-dimensional part of P, then p^{−1}(e) is a tube (an annulus) in ∂M. There are several ways to work with such spines. First, one can allow annular or more complicated components of the corresponding DS-diagrams. However, this is not convenient, since one of the advantages of DS-diagrams is that they deal with 2-cells. Another way consists in forgetting principal edges. This is equivalent to cutting M along proper discs (meridional discs of the solid tubes that correspond to the edges). This is also not very convenient, since one would have to store information on which components of the boundary of the resulting 3-manifold should be joined by tubes. We prefer the third way: spines having points with disconnected links are not considered at all.

2 Simplifying Manifolds and Spines

Let M be a 3-manifold and P its almost simple spine without points with disconnected links. We will simplify M and P by different transformations (moves), which can be divided into four groups. Moves of the first group reduce the cell structures of P and ∂M, but preserve their topological types. Moves of the second and fourth group also preserve M, but change P. The third group consists of surgeries, which change M and P, but only in a controlled manner.

For example, one of the surgery moves cuts off N^{2} ×S^{1} from M, where N^{2} is a disc with two holes. Of course, N^{2} × S^{1} and the remaining piece M_{1} of M do not determine M. In order to reconstruct M, it suffices to know the following:

1. Which tori of ∂M and ∂(N^{2} × S^{1}) should be glued together;

2. Coordinate systems on them;

3. Matrices that determine the gluing homeomorphisms.

This observation motivates our further strategy. On the one hand, we reduce ourselves to considering 3-manifolds whose boundaries consist only of spheres and tori. Some tori must be equipped with coordinate systems. On the other hand, we organize such manifolds into special structures just as chemical atoms are organized into molecules. These structures are called labeled molecules. The exact definition will be given later; for now we describe a convenient way for representing coordinate systems on the boundary tori.

2.1 Coordinate Systems on Tori

Let T be a torus presented as a cell complex. We suppose that T and all its edges are oriented. By a coordinate system on T we mean an ordered pair (μ, λ) of oriented simple closed curves on T with their intersection number 1. We are going to use coordinate systems for describing homeomorphisms of tori by integer matrices. So only the homology classes of μ and λ are essential. Those can be represented by 1-dimensional chains, i.e., by linear combinations μ = ∑_{i=1}^{n} m_{i}e_{i}, λ = ∑_{i=1}^{n} l_{i}e_{i}, where e_{i}, 1 ≤ i ≤ n, are the edges of T and m_{i}, l_{i} are integers.

Further on under a presentation of an oriented 3-manifold M by its cellular spine we mean a set of the following data:

1. An oriented cell complex P whose body is an almost simple spine of M having no points with disconnected links;

2. An oriented nonempty surface (the boundary of M) which consists of spheres and tori and is also presented as an oriented cell complex;

3. A cellular map p: ∂M → P which preserves orientations of all cells;

4. Coordinate systems on some boundary tori presented by ordered pairs of 1-dimensional chains.

Of course, we assume that the orientation of ∂M agrees with the orientation of M. Before considering simplification moves, let us describe an auxiliary move E_{1}. We need it for shifting the coordinate curves aside and clear space for other moves.

Definition 2.1 Let a 3-manifold M be presented by its cellular spine P. Then an edge e ⊂ ∂M is called clean, if either

1. e is contained in a spherical component of ∂M, or

2. e lies on a torus T ⊂ ∂M and the coefficients at e of the coordinate chains μ, λ of T are 0.

E_{1}: Cleaning edges. Let μ = ∑_{i=1}^{n} m_{i}e_{i}, λ = ∑_{i=1}^{n} l_{i}e_{i} be coordinate chains on a torus T ⊂ ∂M. Suppose that ∂C = ∑_{i=1}^{m} ε_{i}e_{i} is the boundary chain of a 2-cell C ⊂ T such that it passes through an edge e_{k} only once, i.e., ε_{k} = ±1. Then we clean e_{k} by replacing μ and λ by the new chains μ′ = μ − m_{k}ε_{k}∂C and λ′ = λ − l_{k}ε_{k}∂C, whose coefficients at e_{k} are 0. Obviously, the new chains determine the same homology classes. A visual interpretation of this move is shown in Fig. 6, where l stands either for μ or for λ.

Figure 6: Instead of passing along e, we go around the remaining part of ∂C

2.2 Reduction of Cell Structures

Now we begin describing the promised moves. Let M be a 3-manifold presented by its cellular spine P. It can happen that the decomposition of P into cells is too complicated. Below we describe several transformations that simplify it. Topological types of M and P remain the same.

R_{1}: Removing vertices of valence 2. Suppose that P contains a vertex A where exactly two different edges a, b meet together. Suppose also that all boundary curves that pass through A do that without returns. It means that a boundary curve is allowed to proceed from a to b or from b to a. Situations when it enters A and goes at once back are forbidden. Then we remove this vertex and amalgamate a, b into a new edge c.

R_{2}: Fusing 2-cells. Let an edge e of P be a common edge of exactly two different 2-cells X, Y of P. Suppose that e is clean (if not, we clean it by applying E_{1}). Then we remove e and amalgamate X, Y to a new 2-cell Z.

R_{3}: Removing needles. Let a be a needle in P, i.e., an edge of valence 2 having a free vertex A. We assume that the needle is not degenerated, i.e., its other vertex is not free. Then we remove a and A.

All three moves are shown in Fig. 7.

Remark 2.2 There is only one case when P contains a degenerated needle: a connected component of P is a 2-sphere decomposed into two vertices, one edge, and one 2-cell. In this case we do not collapse the needle, since after that we would get a 2-sphere without edges. This would be confusing, since the attaching map of the unique 2-cell (which should be presented by a string of integers) would be presented by the empty set.

2.3 Collapses

Let M be a 3-manifold presented by its cellular spine P. Suppose that P contains a free edge a. It means that a lies in the boundary of exactly one 2-cell C of P. We wish to collapse P onto P_{1} = P \ (Inta ∪ IntC). At first glance, this operation is trivial: we simply remove a and C. However, one should be careful, since P_{1} thus obtained can contain points with disconnected links, and we have decided to consider spines without such points. Indeed, there can

Figure 7: Reducing cell decomposition

appear principal edges as well as vertices with disconnected links. To avoid that, we replace the collapse by several more elementary moves that either realize it or reduce to cutting move S_{1}. The first move prevents appearance of principal edges.

C_{1}: Doubling an edge. Let a 2-cell C of P have a free edge a. Suppose that the boundary curve of C passes two or three times through another edge b such that b is not incident to any other 2-cells of P. Then we insert into C a new edge b′ which joins the endpoints of b, see Fig. 8. The new edge decomposes C into a biangle and a new 2-cell C′.

This move improves the cell decomposition of P, since the collapse of C′ through a does not convert b into a free edge while the collapse of C does so.

The second move collapses a 2-cell through its free edge without creating vertices with disconnected links. Let C be a that Let C be a 2-cell of P and l an arc in C joining interior points of two consecutive edges of ∂C. Then l cuts off a triangle from C. We will call this triangle a vertex wing. Of course, creating a vertex wing requires introducing not only a new edge l, but also two new vertices (its endpoints).

C_{2}: Winged collapsing. Suppose that the boundary curve of a 2-cell C of P contains a free edge a and that every other edge of ∂C is incident to at least one 2-cell of P different from C. Let us clean a and insert vertex wings into all corners of C except the ones at the endpoints of a. Then we collapse the remaining part of C through a, see Fig. 9. This move eliminates C completely, Figure 8: Doubling an edge

Figure 9: Winged collapsing

only the wings remain. Thanks to introducing the wings, the links of the vertices are not changed and thus remain connected. Quite often the wings are useless, i.e., the links are still connected without them. The next move allows us to eliminate such superfluous wings.

C_{3}: Collapsing nonseparating wings. Let P contain an embedded triangle 2-cell W having exactly one free edge a (such 2-cells appear under winged collapses). Suppose that the collapse of W through a does not produce vertices with disconnected links. Then we clean a and perform this collapse. If a triangle wing cannot be removed without creating disconnected links, then we convert it into a quadrilateral convenient for performing move S_{1} (see Section 2.4).

C_{4}: Transforming a triangle wing into a quadrilateral with two opposite free sides. Let P contain an embedded triangle 2-cell W having exactly one free edge a. Suppose that the collapse of W through a converts the link of the vertex A opposite to a into a disconnected graph G = G′ ∪ G′′. Then we replace W by a quadrilateral W′ having two opposite free edges. In other words, we stretch up A into a new free edge a′ that joins the cones over the connected components G′, G′′ of G. See Fig. 10, where we illustrate C_{3} and C_{4}.

Figure 10: Working with triangle wings

Figure 11: Cutting a 2-cell

2.4 Surgeries

Let us describe surgery moves. In contrast to reductions and collapses, they can change the manifold. Each time when this happens, we specify which information should be stored in order to enable the reconstruction of the original manifold. Let M be a 3-manifold presented by its cellular spine P.

S_{1}: Cutting 2-cells. Suppose that a 2-cell C of P contains two free edges a, b such that they cannot be joined by a chain of consecutive free edges of C. Let us join a middle point of a with a middle point of b by a proper arc l in C. Then we cut P along l, see Fig. 11.

Obviously, the resulting polyhedron P_{1} is a spine of a 3-manifold M_{1} obtained by cutting M along a proper disc D ⊂ M such that D∩P = l. Let us investigate the relation between M and M_{1}. There are three cases.

Case 1. Suppose D separates M into two components M′ and M′′. Then M = (M′ ∪ D^{3})#M′′, where the notation M′ ∪ D^{3} means that we fill up a boundary sphere of M′ with a 3-ball. To get a sphere S that separates M into the connected sum, it suffices to take ∂M′ and slightly push it inside M.

Case 2. Suppose ∂D separates the component F of ∂M it is contained in, but D does not separate M. Then M = (M_{1} ∪ D^{3})#(S^{2} × S^{1}). Indeed, let F′, F′′ be the two components of ∂M_{1} obtained from F. Recall that F is either a sphere or a torus. Therefore, at least one of the surfaces F′, F′′ is a 2-sphere. If we push it inside M, we get a nonseparating sphere S in M. The existence of such sphere explains the appearance of the summand S^{2} × S^{1}.

Case 3. Suppose that ∂D does not separate the component F of ∂M it is contained in. Then M = (M_{1} ∪ D^{3})#(D × S^{1}). Of course, in this case F is a torus. Compressing it along D and pushing inside M, we get a 2-sphere S decomposing M into the connected sum.

Let us specify what information is required for reconstructing M from M_{1}. Filling the spherical boundary components with 3-balls can be done in a unique way. Since we are working with oriented 3-manifolds, connected sums are also uniquely determined by the summands. So M can be reconstructed quite easily in all three cases.

However, if the component T of ∂M containing ∂D is a torus, then one should take care of the coordinate curves μ, λ on it. In the first two cases we simply use E_{1} to shift μ, λ away from the copies ã, b̃ of a, b in ∂M. This is possible, since ∂D bounds a disc in T. Case 3 is slightly more difficult. Note that, up to twists of the solid torus V = D × S^{1} along a meridional disc D = D × {∗}, any pair of coordinate curves on ∂V is completely determined by their intersection numbers w_{1}, w_{2} with ∂D. These numbers can be calculated quite easily. Indeed, denote by m_{a}, m_{b} the coefficients of μ at the edges ã, b̃ ⊂ T, and by l_{a}, l_{b} the corresponding coefficients of λ. Suppose that ã, b̃ are oriented coherently as shown in Fig. 11. Then w_{1} = m_{a} + m_{b}, w_{2} = l_{a} + l_{b}. Of course, if ã, b̃ have opposite orientations, then w_{1} = m_{a} − m_{b}, w_{2} = l_{a} − l_{b}. These two numbers (they are called the weights of the cut) should be stored for the future reconstruction of M.

S_{2}: Delicate piercing. Suppose that ∂M consists of at least two components, and at least one of them is a sphere. Then we can find a 2-cell C of P that separates a spherical component S of ∂M from another one. It means that one of the two copies of C in ∂M lies in S while the other one is contained in a different component of ∂M. Choose a disc D ⊂ IntC and join it with a vertex of C by a simple arc. Then the piercing consists in removing IntD from P, see Fig. 12.

We have called this piercing delicate since it induces a very mild modification of M. Indeed, the new manifold M_{1} is homeomorphic to a 3-manifold obtained from M by filling up a spherical boundary component with a 3-ball. Of course, all points of the new spine P_{1} have connected links (for this reason we do not remove the whole cell C but make only a small hole).

S_{3}: Rough piercing. We apply this move only in case when ∂M = S^{2} and all opportunities for other simplification moves have already been exhausted. In particular, P must be special. Let C be a 2-component of P. To apply S_{3}, we do the same as in the case of S_{2}. We choose a disc D ⊂ IntC, join it with a vertex of C by a simple arc, and remove IntD from P.

Rough piercing transforms M into a new 3-manifold M_{1} whose boundary T

Figure 12: Piercing

Figure 13: Coordinate curves on the boundary torus

is a torus. According to our rule, we should introduce coordinate curves on T. We do that as follows. The first curve μ ⊂ T corresponds to ∂D, the second curve λ is an arbitrary closed curve in T which crosses μ exactly once. See Fig. 13. Of course, we orient μ and λ appropriately.

S_{4}: Cutting along a proper annulus with nontrivial boundary components. Suppose that a 2-component α of P contains a nontrivial orientation-preserving simple closed curve l. We assume that l intersects edges of P transversally. Let A be a proper annulus in M such that A∩P = l. We assume that the boundary circles of A are nontrivial in ∂M (see move U_{1} in Section 2.5 for the case when at least one of them is trivial). Then we cut P along l and M along A, see Fig. 14 (only a half of A is shown).

The new spine P_{1} of the new manifold M_{1} obtained by the cut contains n pairs of new vertices and n pairs of new free edges, where n is the number of intersection points of l with the edges.

Let us investigate what information should be stored to enable the subsequent reconstruction of M from M_{1}. Denote by L the connected component of A ∪ ∂M that contains A. It consists of A and one or two boundary tori. Let Y be a regular neighborhood of L in M such that P_{1} is contained in the manifold Cl(M \Y), which can be identified with M_{1}. Then P_{1} is a spine of M_{1}, M = M_{1} ∪ Y, and M_{1} ∩ Y consists of one or two common boundary tori. Since

Figure 14: Cutting along a circle

Figure 15: Y = Cl(M \ M_{1}) is an orientable circle bundle over N^{2} or M_{0}^{2}

the boundary circles of A are nontrivial in ∂M, L fibers onto circles. It follows that Y is a circle bundle over a surface F. It is easy to see that χ(F) = −1 and ∂F consists of three or two circles. Therefore, F is homeomorphic either to a twice punctured disc N^{2} or to a once punctured Möbius band M_{0}^{2}. The second option takes place when the coherently oriented boundary circles of A lie on the same boundary torus of M and have opposite orientations there. See Fig. 15, where we show 2-dimensional pictures. We may conclude that Y = N^{2} × S^{1} or Y = M_{0}^{2} ˜×S^{1}.

A coordinate system on every torus T ⊂ Y ∩ M_{1} can be chosen arbitrarily, but the most natural choice for λ is an arbitrarily oriented boundary circle of ∂A contained in T. Of course, the circle should be replaced by a curve composed of edges, i.e., by a homologous 1-chain. The choice of μ doesn’t really matter; one can take any curve on T crossing λ once. The only thing we should take care of is its orientations: the orientation of μ considered as a curve on ∂M_{1} must be opposite to its orientation as a curve in ∂Y.

However, we face the following problem. Since M_{1} is presented by its spine P_{1}, the coordinate systems on the tori of ∂M_{1} can be presented as usual, i.e., by 1-chains. In contrast to this, Y is not endowed with a spine. How can we describe the coordinate curves on ∂Y? We must do that for the new curves on the tori Y ∩ M_{1} as well as for the curves on the tori Y ∩ ∂M, which determine coordinate systems on the toral components of ∂M. Solution of this problem is simple. Suppose that Y = N^{2} ×S^{1}. Let T_{i}, 1 ≤ i ≤ 3, be the boundary tori of Y and (μ_{i}, λ_{i}) the coordinate curves on them. Choose canonical coordinate curves (s_{i}, f_{i}) on T_{i}, where s_{i} is the boundary circle of N^{2} × {∗} contained in T_{i} and f_{i} is a fiber. Then μ_{i}, λ_{i} can be written in the form μ_{i} = s_{i}^{a_{i}}f_{i}^{b_{i}}, λ_{i} = s_{i}^{c_{i}}f_{i}^{d_{i}}, i.e.,

they can be represented by the unimodular (2 × 2)-matrix A_{i} = ( \begin{matrix}a_{i} & b_{i} \\ c_{i} & d_{i} \end{matrix} ).

If Y = M_{0}^{2} ˜×S^{1}, then we do the same. Choose a section F ⊂ Y, i.e., a surface intersecting each fiber at exactly one point. F is of course homeomorphic to M_{0}^{2}. The canonical coordinate systems (s_{i}, f_{i}) on the boundary tori T_{i}, i = 1, 2, of Y are composed of the boundary circles of F and fibers. The matrices A_{1}, A_{2} representing the systems have the same meaning: they express μ_{i}, λ_{i} through (s_{i}, f_{i}).

S_{5}: Cutting along a theta-curve. Suppose that M contains a proper punctured torus T_{0} such that Θ = T_{0} ∩ P is a theta-curve which does not separate T_{0}, and C = ∂T_{0} is contained in a spherical component S of ∂M. We supply T_{0} with a coordinate system (μ, λ) composed of two distinct circles contained in Θ. Then we cut M along T_{0} and P along Θ. The manifold M_{1} obtained in this way contains two new toral boundary components T_{±}, each consisting of a copy of T_{0} and a disc of S. We supply them with coordinate systems (μ_{±}, λ_{±}) composed of the copies of μ and λ. Again, the orientations of λ_{±} determine the same orientation of λ while the orientations of μ_{±} correspond to the opposite orientations of μ.

Let us describe a method for finding a torus T_{0} which satisfies the above conditions. For simplicity, we consider only the case when the spine P is special and its cell structure is reduced, i.e., coincides with the intrinsic decomposition of P into true vertices, triple edges, and 2-components. Suppose that there exist two edges a, b and three 2-cells C_{1}, C_{2}, C_{3} of P such that their boundary curves, being properly oriented, pass through a in the same direction and pass through b also in the same direction. Let us choose two points A ∈ a, B ∈ b and join them by three arcs l_{i} ⊂ C_{i}, 1 ≤ i ≤ 3. We get a theta-curve Θ ⊂ P such that its regular neighborhood N(Θ) in P is Θ×I and thus consists of three strips joining a subarc of a with a subarc of b. Suppose that each of these strips approaches the union of the other two from different sides, see Fig. 16 to the left. Then the inverse image C = p^{−1}(Θ) under the projection map p: ∂M → P is a circle in ∂M bounding a proper punctured torus T_{0} ⊂ M such that T_{0} ∩ P = Θ, see Fig. 16 to the right. If C is contained in a spherical component of ∂M, then move S_{5} is applicable.

S_{6}: Cutting along a theta-curve and adding a torus. This move is a twin of S_{5}. Suppose M contains a proper punctured torus T_{0} such that Θ = T_{0} ∩ P is a theta-curve, C = ∂T_{0} is contained in a toral component of ∂M, and C bounds a disc D ⊂ ∂M. Such punctured tori, if they exist, can be found by the same method as above. We supply T_{0} with a coordinate system (μ, λ) composed of two distinct circles contained in Θ. This time we cannot cut M along T_{0}, since then we would obtain a manifold with a genus two surface in the boundary. The procedure is slightly more complicated. First, we push the torus T_{0} ∪ D inward and get a torus T ⊂ IntM parallel to T_{0}∪D. Then we cut M along T and supply both boundary tori created in this way by the coordinate systems inherited from the system (μ, λ) on T_{0}. A spine P_{1} of the new manifold M_{1} obtained in this Figure 16: A regular neighborhood of Θ in P and the transversal punctured torus

Figure 17: Cutting M along a torus intersecting P at a theta-curve

way can be constructed as follows. We replace P by a polyhedron P ∪T_{−}, where T_{−} is a parallel copy of T placed between T and T_{0} ∪ D. Then we cut P along the theta-curve T ∩ P, see Fig. 17.

Remark 2.3 Move S_{5} considered above produces a spine P_{1} which has free edges and thus can be collapsed onto a smaller spine. In fact, the combined move (cutting along a theta-curve and collapsing) is very powerful, since it entirely eliminates the cells C_{1}, C_{2}, C_{3} of P that intersect T_{0}.

The situation with the move S_{6} is more delicate. On one hand, adding T_{−} to P creates two new vertices, whose links are even more complicated than the link of the standard true vertex. On the other hand, cutting and collapsing destroys three half-cells and all true vertices contained in their boundaries. Therefore, in order to have a real simplification, we should take care that the number k of such vertices be at least 3. One can easily show that, since C_{1}, C_{2}, C_{3} are distinct, k is always greater than one. Moreover, k = 2 if and only if T cuts off from M a piece which contains exactly two true vertices of P. This piece is always homeomorphic either to a thick torus T^{2} × S^{1} or to a solid torus D^{2} × S^{1}.

2.5 Disc Replacement Moves

We are now going to describe the last portion of transformations. Let M be an oriented 3-manifold presented by its simple cellular spine P. Any disc replacement can be considered as 2-cell trading: we attach to P a new 2-cell D ⊂ M

Figure 18: A disc replacement move

and remove another one. The manifold remains the same. We define here a general disc replacement move and then describe some specific versions which quite often simplify P.

Let us identify M with a close regular neighborhood of P. Suppose ℓ̃ is a trivial circle on ∂M. Denote by ℓ the closed curve p(ℓ̃) ⊂ P, where p: ∂M → P is the standard projection. We always assume that ℓ is in general position, i.e., intersects the edges of P and itself transversally. Since ℓ̃ bounds a disc in ∂M, there is a disc D in M with the embedded interior (but maybe with selfintersecting boundary) such that ∂D = ℓ and D has no other common points with P. Then D cuts off from M \P a 3-ball B. Let C ≠ D be a 2-component of the simple polyhedron P′ = P ∪ D which separates B from another component of M \ P′. Removing from C an open disc, i.e., performing a delicate piercing (move S_{2}), we get another simple spine P_{1} of M. We say that P_{1} is obtained from P by a disc replacement move, see Fig. 18.

Note that addition of D creates new true vertices at self-crossings of ℓ and at points where ℓ crosses the triple edges of P. The total number of such vertices is called the length of the move. We are mainly interested in cases when, after collapsing P_{1}, we get an almost simple polyhedron P_{2} which is simpler than P (recall that we measure the complexity of an almost simple polyhedron X by the number c(X) of its true vertices).

Definition 2.4 A disc replacement move is called admissible if the following conditions are satisfied:

1. The length of the move does not exceed 4. It means that the addition of D creates no more than 4 new true vertices, i.e., c(P_{1}) − c(P) ≤ 4.

2. The combined move (attaching D, piercing, and collapsing) does not increase c(P), i. e. c(P_{2}) ≤ c(P).

An admissible disc replacement move is called monotone if c(P_{2}) < c(P), and horizontal if c(P_{2}) = c(P).

We describe several admissible disc replacement moves. The first move has length 0.

Figure 19: Attaching D^{2} along l and puncturing another 2-component produces a simpler spine

U_{1}: ℓ has length 0. Let D be a disc in IntM such that D ∩ P = ∂D is a nontrivial embedded circle in a 2-component C of P. Then we attach D to P and perform a delicate piercing. See Fig. 19.

It is easy to see that this move is admissible. We do not create new true vertices while some true vertices and triple lines may disappear under collapsing. In any case, C becomes simpler, since its Euler characteristic increases.

Again, we want a simple method for finding a disc D and a circle ℓ satisfying the required conditions. Here is one. Let C̃ be the inverse image of a 2-components C of P under the projection p: ∂M → P. Then C̃ is either the union of two copies of C or a 2-sheeted covering of C, depending on whether or not C is two-sided. In both cases C̃ contains a circle trivial in ∂M and nontrivial in C if and only if such a circle can be found among boundary components of C̃. It follows that we need to consider only those circles in C̃ which are parallel to ∂C̃. In our situation, when ∂M consists of spheres and tori, all boundary circles of C̃ are nontrivial only if C̃ is either a nontrivial annulus in a toral component of ∂M or the union of two such annuli.

Further on we consider only the case when P is special and its cell structure is reduced, i.e., coincides with the intrinsic decomposition of P into true vertices, triple edges, and 2-components. Recall that then M possesses the induced cell decomposition (DS-diagram). We describe all possible curves of length ≤ 4 which bound discs in the complement of P and thus can be used for performing disc replacement moves. It turns out that in all these cases a place for piercing can be chosen so that the resulting move be admissible, i.e., is either monotone or horizontal. Altogether, there are five such moves.

The moves are presented by pictures, each consisting of two parts. The left part shows a circle ℓ̃⊂ M contained in a sub-disc of ∂M. The places where we can potentially puncture P ∪D are marked by asterisks. The right part shows a regular neighborhood in P of ℓ. Of course, the collapse destroys all true vertices at the boundary of a chosen asterisked region.

U_{2}: ℓ is of length 1. Denote by C the 2-component of P whose closure contains ℓ and by a the edge of P intersecting ℓ. Then the boundary curve of C has a counterpass on ℓ. So the move is monotone, since after puncturing and collapsing there disappears not only the new true vertex, but also at least one

Figure 20: ℓ is of length 1

Figure 21: ℓ is an embedded circle of length 2

old vertex. See Fig. 20.

U_{3}: ℓ is of length 2. In this case the combined move (U_{3} plus collapsing) destroys both new vertices, see Fig. 21. It is always monotone, except the situation when ℓ crosses the same edge twice and the move produces a homeomorphic spine.

U_{4}: ℓ is of length 3 and has no self-intersections. The corresponding combined move destroys two new vertices and at least one old vertex. Moreover, if ℓ is not contained in a regular neighborhood of a true vertex, then one of the three asterisked 2-components contains at least two old vertices. So the move can be made monotone by a right choice of a 2-component for piercing. See Fig. 22.

U_{5}: ℓ is of length 4 and has no self-intersections.

U_{6}: ℓ is of length 4 and has one self-intersection.

Figure 22: ℓ is of length 3 and has no self-intersections

Figure 23: ℓ is an embedded circle of length 4

Figure 24: ℓ is of length 4 and has one self-intersection

In these two cases at least one of the asterisked 2-components contains two new and at least two old vertices. Therefore, both moves are at least horizontal. See Fig. 23, 24.

One can easily show that moves U_{2}−U_{6} exhaust all types of disc replacement moves on special spines such that addition of the new disc creates ≤ 4 true vertices.

3 Labeled molecules

In this section we use a convenient terminology introduced by A. Fomenko for investigation of integrable Hamiltonian systems [3, 1].

3.1 What is a labeled molecule?

A labeled molecule is an arbitrary graph G, some of whose vertices and edges are equipped with labels of different kind, see Fig. 25.

There are five types of vertices and two types of edges. Labeled vertices are called atoms. Let us describe them.

1. Solid torus vertices. They have valence 1 and are shown by fat black dots.

2. Möbius vertices. They are of valence 2 and labeled by white circles.

Figure 25: Edges labeled by matrices join atoms of different types into a labeled molecule

3. Triple vertices. They have valence 3 and no label.

4. Exceptional vertices. Each such vertex stands for an oriented 3-manifold X presented by its simple spine P and a map ∂X → P. The boundary of X consists of spheres and tori. We assume that there is a fixed bijection between the boundary tori of X and the edges of G having an endpoint at the vertex (if an edge has both endpoints at the vertex, then it corresponds to two boundary tori). The boundary tori which are joined by edges with vertices of types 1 - 4 are equipped with coordinate systems.

5. Virtual vertices. They are of valence 1 and not labeled.

These labels have a clear meaning. Vertices of the first three types correspond to standard 3-manifolds and are considered as known atoms. Each Möbius atom is an oriented S^{1}-bundle M_{0}^{2} ˜×S^{1} over a once punctured Möbius strip M_{0}^{2}. Since M_{0}^{2} is homeomorphic to the twice punctured projective plane, the boundary tori are symmetric in the sense that they are related by an orientation preserving involution of the bundle. We equip the tori with coordinate systems such that the meridians are the boundary components of a section of the bundle while the longitudes are fibers. The meridians and longitudes are oriented so that the intersection number of each meridian with the corresponding longitude be 1. There are four choices of such orientations. Any two of them are related by an orientation-preserving homeomorphism of M_{0}^{2} ˜×S^{1}.

Triple vertices correspond N^{2} × S^{1}, where N^{2} is a twice punctured disc. We introduce coordinate systems on the boundary tori of N^{2} × S^{1} in the same way as above: meridians are the oriented boundary circles of a section, the longitudes are oriented fibers, and the intersection number of each meridian with the corresponding longitude is 1. Of course, solid torus vertices correspond to solid tori with the standard meridian-longitude coordinate systems. Since any two longitudes of a solid torus are related by a homeomorphism of the torus, it does not matter which system is chosen.

Exceptional atoms can correspond to known 3-manifolds, for example, to hyperbolic 3-manifolds contained in known tables [15, 4] or to complements of tabulated knots [5, 13]. They can also correspond to 3-manifolds which are unknown in the sense that we only know their simple spines.

Virtual vertices correspond to empty atoms. They are introduced to indicate the valences of other atoms and stand for their toral boundary components.

Let us describe the edges of G. They can be divided into two groups: true edges with vertices of types 1 - 4 and virtual edges that have a virtual vertex. True edges are oriented and labeled by order 2 matrices with determinant (-1). Virtual edges have no labels.

At last, we assume that any labeled molecule is equipped with three global labels (g_{1}, g_{2}, g_{3}), which are nonnegative integers. They tell us how many 3balls, solid tori, and copies of S^{2} × S^{1} have been cut off during construction the molecule.

It turns out that any labeled molecule G determines a connected 3-manifold M(G) whose boundary consists of spheres and tori. To reconstruct M(G), we take into account the meaning of atoms and edge labels. Even this information allows us to compose a 3-manifold M′(G) as follows. We replace each vertex v of type 1 - 4 by a copy of the corresponding manifold. The boundary tori of this manifold are parameterized by the edges that have an endpoint in v. If e is a true edge, then the corresponding tori are equipped with coordinate systems, and e is labeled with a matrix. We glue together the manifolds that correspond to endpoints of e via a homeomorphism described by the matrix. Of course, if G is disconnected, then so is the obtained 3-manifold M′(G). In this case we replace it by the connected sum of all its components (since we are considering only oriented manifolds, the connected sum is well-defined). We denote the connected sum also by M′(G).

Then what is the role of the global labels g_{1}, g_{2}, g_{3}? To get M(G), we add to M′(G) exactly g_{1} copies of the standard 3-ball. This is equivalent to puncturing M′(G) g_{1} times. Then we add g_{2} copies of the solid torus and g_{3} copies of the manifold S^{2} × S^{1}. In other words,

M(G) = M′(G)#g_{1}B^{3}#g_{2}(D^{2} × S^{1})#g_{3}(S^{2} × S^{1}).

3.2 Creating a labeled molecule

What we have said in the previous section implies that each labeled molecule determines a manifold. Now we go in the opposite direction. Let M be an oriented 3-manifold whose boundary consists of spheres and tori. We describe a procedure that assigns to M a labeled molecule G such that M = M(G). Of course, Of course, we wish the atoms be as simple as possible.

We begin with constructing a special spine P of M and creating a molecule G_{0} consisting of only one exceptional atom M labeled with P. The atom has

Figure 26: Action of S_{1} onto labeled molecules

only virtual outgoing edges. Then we apply to G_{0} and all labeled molecules arising in this way all moves described in Section 2 as long as possible.

Moves E_{1} (cleaning edges) and R_{1} −R_{3} (reductions of cells) do not affect the molecule. Moves C_{1} − C_{4} (collapses) as well as disc replacement moves D_{1} − D_{7} modify the spines of exceptional vertices. The molecules remain the same. In contrast to this, surgeries S_{1}−S_{6} do change the labeled molecules. Suppose that we apply move S_{i} to an exceptional atom X of G represented as a thickening of its simple spine P.

Move S_{1}. Recall that this move consists in cutting X and P along a proper disc D ⊂ X and along the arc l = D ∩ P, respectively. It either divides X into two new atoms (Case 1), or replaces (X, P) by a new pair (X′, P′) and increases the global label g_{3} by 1 (Case 2), or tears off from X a solid torus (Case 3). See Fig. 26, where we show the first two possibilities and two versions of the third one. Which possibility takes place depends on the behavior of D, see the description of move S_{1}. If ∂D is a nonseparating curve in a torus T ⊂ ∂X, then we take into account the type of the edge e of G corresponding to T. If e is virtual, then we remove e and add 1 to g_{2}. If e is true, then we cut off a solid torus atom V together with e. The matrix A for e should be replaced by the new matrix A′ which determines the same gluing map, but is written for a standard coordinate system on V.

Moves S_{2}, S_{3}. Delicate piercing S_{2} replaces the pair (X, P) by a new pair (X′, P′) and increases the global label g_{1} by 1. Rough piercing S_{3} transforms an exceptional atom of valence 0 into a new atom joined with a unique solid

torus atom by an edge. The edge is labeled by the matrix Ē = ( \begin{matrix}−1 & 0 \\ 0 & 1 \end{matrix} ), see

Fig. 27 to the left.

Move S_{4}. This move consists in cutting X and P along a proper annulus A ⊂ X and the circle l = A ∩ P, respectively. A cuts off from X a new atom Y homeomorphic to either N^{2} ×S^{1} or M_{0}^{2} ˜×S^{1}. The corresponding transformation of the molecule is shown in Fig. 27 to the right. There are three cases, depending on the type of Y and the number of edges that join Y with the remaining part X′ of X. The new matrices A′, B′ determine the same gluing maps, but are Figure 27: How S_{2}, S_{3}, S_{4} transform molecules

Figure 28: How S_{5}, S_{6} transform molecules

written for a standard coordinate system on Y.

Moves S_{5}, S_{6}. These moves consist in cutting X along a torus intersecting P along a theta-curve Θ. In the case of move S_{5} the torus is punctured and its boundary is contained in a spherical component of ∂X. In the case of move S_{6} the torus is closed and lies in the interior of X. In both cases we cut P along Θ. The corresponding transformation of the molecule depends on whether or not Θ splits P into two parts. We replace X either by two new atoms joined by a new edge, or by one new atom with a new loop, see Fig. 28. We label the new edge by the matrix Ē, since the coordinate systems on the corresponding boundary tori are composed of appropriately oriented copies of the same circles in Θ.

3.3 Assembling Seifert atoms

Let G be a labeled molecule obtained for a 3-manifold M by the procedure described above. Note that the atoms of the first three types (solid tori, M_{0}^{2} ˜×S^{1}, N^{2} × S^{1}) are Seifert manifolds. Now we begin the reverse process of assembling them into larger Seifert manifolds. Combined Seifert atoms thus obtained will be labeled by squares. We can consider each square as a closed box containing complete information about the corresponding Seifert manifold M and the coordinate systems on its boundary tori.

Let us describe a convenient way of storing this information. We present M in the form M = M(F, (p_{i}, q_{i}), 1 ≤ i ≤ n), where F is the base surface and (p_{i}, q_{i}) are nonnormalized Seifert invariants of n ≥ 0 distinguished fibers such that all exceptional fibers (i.e., fibers with p ≠ ±1) are included. Having this information, we can reconstruct M as follows. Let a surface F_{0} be obtained from F by cutting out n disjoint discs D_{i}, 1 ≤ i ≤ n. Consider an oriented circle bundle M_{0} over F_{0}, i.e., an orientable direct or skew product of F_{0} and S^{1}. If F is orientable, then the product is direct, otherwise twisted. In both cases it admits a section S ⊂ M_{0}. We endow the tori of ∂M_{0} with coordinate curves (μ_{i}, λ_{i}), where μ_{i} is a boundary circle of the section and λ_{i} is a fiber. Of course, μ_{i}, λ_{i} should be properly oriented.

In order to get M, we attach solid tori V_{i}, 1 ≤ i ≤ n, so that the meridian of each torus V_{i} be mapped to a circle of the type p_{i}μ_{i} + q_{i}λ_{i}.

Remark 3.1 The difference between normalized and nonnormalized Seifert invariants of exceptional fibers is that in the first case we require 0 < q_{i} < p_{i}. If the manifold is closed, then the normalized invariants do not determine it; it is necessary to know normalized invariants do not determine it; it is necessary to know one one additional integer parameter. In the second case q_{i} can be an arbitrary number coprime to p_{i}, and no additional parameters are needed.

Let us describe two assembling moves.

Move A_{1}: Adjoining a solid torus atom. Let a molecule contain a solid torus atom V such that the other vertex of the only outgoing edge e is a Seifert atom

X. Suppose that the matrix label of e has the form ( \begin{matrix}a & b \\ c & d \end{matrix} ) such that a ≠ 0.

It means that the corresponding attaching map φ: ∂V → ∂X takes the meridian of V to a curve which is not a longitude or, equivalently, that the preimages of fibers are not meridians. Then we remove V and replace X by the combined Seifert atom X′ = X ∪_{φ} V. The base surface F′ of X′ is obtained from the base surface F of X by attaching a disc to the corresponding circle of ∂F. Also, X′ obtains an additional distinguished fiber with Seifert invariants (a, c).

Move A_{2}: Uniting two Seifert atoms. Suppose that two Seifert atoms X_{1}, X_{2}

are joined by an edge e with the label of the form ( \begin{matrix}−a & 0 \\ c & a \end{matrix} ), where a = ±1.

It means that the gluing map between the corresponding tori of ∂X_{1}, ∂X_{2} takes fibers to fibers. Then we replace X_{1}, X_{2} by the combined Seifert atom X′ = X_{1} ∪_{φ} X_{2}. The base surface F′ of X′ is obtained by the induced gluing of the base surfaces of X_{1}, X_{2}. The set of distinguished fibers of X′ consists of those of X_{1} and X_{2} with the same Seifert invariants, and of one additional regular fiber with parameters (1, c) if a = 1 and (1, −c) if a = −1. See Fig. 29.

Figure 29: Assembling moves

4 The Algorithm

Let M be a 3-manifold whose boundary is either empty or consists of tori. Let G be a labeled molecule obtained for a 3-manifold M by the disassembling process described above. Suppose that G contains only atoms of the first three types (solid tori, M_{0}^{2} ˜×S^{1}, N^{2} × S^{1}), which are Seifert manifolds. Then we begin the reverse process of applying to G assembling moves A_{1}, A_{2} as long as possible.

Suppose that the process stops at a molecule with only one atom and g_{3} = 0. Then this atom coincides with the original manifold M, but this time we know the Seifert structure of M. In this case the the algorithm gives us the name, i.e., the base of M and Seifert invariants of exceptional fibers.

If we get a connected molecule with several Seifert atoms, then it determines a graph manifold of Waldhausen [14], together with its canonical decomposition into Seifert manifolds. Of course, in order to recover M, one should add g_{2} solid tori and g_{3} copies of S^{2} × S^{1}. There is only one exceptional case, when there is an atom of the type (S^{2}, (2, 1), (2, −1). Then it is allowed to choose on it another Seifert structure, i.e., present it as M^{2} ˜×S^{1}, and continue the process. Of course, the reverse replacement is also allowed.

In case we get a disconnected molecule, then M is the connected sun of 3-manifolds that correspond to the connected components of the molecule.

At last, in case the disassembling process produces a molecule containing non-Seifert atoms, we still get a decomposition of M into Seifert manifolds and a few unknown pieces, which quite often coincides with the JSJ-decomposition, see [7, 12, 11].

References

[1] Bolsinov, A. V.; Matveev, S. V.; Fomenko, A. T. Topological classification of integrable Hamiltonian systems with two degrees of freedom. A list of systems of small complexity. (Russian) Usp. Mat. Nauk 45 (1990), no. 2(272), 49–77, 240; translation in Russian Math. Surveys 45 (1990), no. 2, 59–94.

[2] Casler, B. G. An imbedding theorem for connected 3-manifolds with boundary. Proc. Amer. Math. Soc. 16 1965 559–566.

[3] Fomenko, A. T. The topology of surfaces of constant energy of integrable Hamiltonian systems and obstructions to integrability. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 50 (1986), no. 6, 1276–1307, 1344.

[4] Hildebrand, Martin; Weeks, Jeffrey A computer generated census of cusped hyperbolic 3-manifolds. Computers and mathematics (Cambridge, MA, 1989), 53–59, Springer, New York, 1989.

[5] Hoste, Jim; Thistlethwaite, Morwen; Weeks, Jeff The first 1,701,936 knots. Math. Intelligencer 20 (1998), no. 4, 33–48.

[6] Ikeda, Hiroshi; Inoue, Yoshinobu Invitation to DS-diagrams. Kobe J. Math. 2 (1985), no. 2, 169–186.

[7] Jaco, William H.; Shalen, Peter B. Seifert fibered spaces in 3-manifolds. Mem. Amer. Math. Soc. 21 (1979), no. 220, viii+192 pp.

[8] Klette, R. Cell complexes through time. Proc. Vision Geometry IX, San Diego, SPIE-4117(2000), 134-145.

[9] Kovalevsky, V. A. Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Processing 46(1989), 141-161.

[10] Matveev, S. V. Transformations of special spines, and the Zeeman conjecture. (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 51 (1987), no. 5, 1104– 1116, 1119; translation in Math. USSR-Izv. 31 (1988), no. 2, 423–434

[11] Matveev, S. V. Generalized graph manifolds and their efficient recognition. (Russian) Mat. Sb. 189 (1998), no. 10, 89–104; translation in Sb. Math. 189 (1998), no. 9-10, 1517–1531.

[12] Neumann, Walter D., Swarup, Gadde A. Canonical decompositions of 3manifolds. Geom. Topol. 1 (1997), 21–40 (electronic).

[13] Rolfsen, Dale Knots and links. Mathematics Lecture Series, No. 7. Publish or Perish, Inc., Berkeley, Calif., 1976. ix+439 pp.

[14] Waldhausen, Friedholm Eine Klasse von 3-dimensionalen Mannigfaltigkeiten. I, II. Invent. Math. 3 (1967), 308–333; ibid. 4 1967 87–117.

[15] Weeks, J. Hyperbolic Structures on 3-manifolds Ph. D. Thesis, Princeton University, 1985.