A census of genus-two 3-manifolds up to 42 coloured tetrahedra

We improve and extend to the non-orientable case a recent result of Karábaš, Mali?ký and Nedela concerning the classification of all orientable prime 3-manifolds of Heegaard genus two, triangulated with at most 42 coloured tetrahedra.     

Boundary slopes of non-orientable Seifert surfaces for knots

We study non-orientable Seifert surfaces for knots in the 3-sphere, and examine their boundary slopes. In particular, it is shown that for a crosscap number two knot, there are at most two slopes which can be the boundary slope of its minimal genus non-orientable Seifert surface, and an infinite family of knots with two such slopes will be described. Also, we discuss the existence of essential non-orientable Seifert surfaces for knots.     

Regular maps on non-orientable surfaces

It is well known that regular maps exist on the projective plane but not on the Klein bottle, nor the non-orientable surface of genus 3. In this paper several infinite families of regular maps are constructed to show that such maps exist on non-orientable surfaces of over 77 per cent of all possible genera.     

The bondage number of graphs on topological surfaces and Teschner’s conjecture

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner’s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.     

Schnyder woods for higher genus triangulated surfaces (abstract)

We study a well known characterization of planar graphs, also called Schnyder wood or Schnyder labelling, which yields a decomposition into vertex spanning trees. The goal is to extend previous algorithms and characterizations designed for planar graphs (corresponding to combinatorial surfaces with the topology of the sphere, i.e., of genus 0) to the more general case of graphs embedded on surfaces of arbitrary genus. We define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and colouration of the edges that extends the one proposed by Schnyder for the planar case. As a by-product we show how to characterize our edge coloration in terms of genus g maps.     

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.     

Equivelar Polyhedra with Few Vertices

We know that the polyhedra corresponding to the Platonic solids are equivelar. In this article we have classified completely all the simplicial equivelar polyhedra on ≤ 11 vertices. There are exactly 27 such polyhedra. For each n\geq -4 , we have classified all the (p,q) such that there exists an equivelar polyhedron of type {p,q} and of Euler characteristic n . We have also constructed five types of equivelar polyhedra of Euler characteristic -2m , for each m\geq 2 . Received February 14, 2000, and in revised form August 15, 2000. Online publication March 26, 2001.     

Reducing Dehn Fillings and Small Surfaces

In this paper we investigate the distances between Dehn fillingson a hyperbolic 3-manifold that yield 3-manifolds containingessential small surfaces including non-orientable surfaces.In particular, we study the situations where one filling createsan essential sphere or projective plane, and the other createsan essential sphere, projective plane, annulus, Möbiusband, torus or Klein bottle, for all eleven pairs of such non-hyperbolicmanifolds. 2000 Mathematics Subject Classification 57M50.     

Irreducible Triangulations of Surfaces with Boundary

A triangulation of a surface is irreducible if no edge can be contracted to produce a triangulation of the same surface. In this paper, we investigate irreducible triangulations of surfaces with boundary. We prove that the number of vertices of an irreducible triangulation of a (possibly non-orientable) surface of genus g ≥ 0 with b ≥ 0 boundary components is O(g + b). So far, the result was known only for surfaces without boundary (b = 0). While our technique yields a worse constant in the O(.) notation, the present proof is elementary, and simpler than the previous ones in the case of surfaces without boundary.     

Polyhedral 2-manifolds inE 3 with unusually large genus

An equivelar polyhedral 2-manifold in the class ?_p,q is one embedded inE ³ in which every face is a convexp-gon and every vertex isq-valent. In this paper, examples are constructed, to show that each of the classes ?_3,q (q≧7), ?_4,q (q≧5) and ?_p,4 (p≧5) contains infinitely many distinct combinatorial types. As particular examples, there are polyhedral 2-manifolds with 576 vertices and genus 577, and with 4096 faces and genus 4097. A modification of one construction shows that there is a constantk, such that for eachg≧2, there exists a closed polyhedral 2-manifold inE ³ of genusg with at mostkg/logg vertices.     

A New Approach to Crushing 3-Manifold Triangulations

The crushing operation of Jaco and Rubinstein is a powerful technique in algorithmic 3-manifold topology: it enabled the first practical implementations of 3-sphere recognition and prime decomposition of orientable manifolds, and it plays a prominent role in state-of-the-art algorithms for unknot recognition and testing for essential surfaces. Although the crushing operation will always reduce the size of a triangulation, it might alter its topology, and so it requires a careful theoretical analysis for the settings in which it is used. The aim of this short paper is to make the crushing operation more accessible to practitioners and easier to generalise to new settings. When the crushing operation was first introduced, the analysis was powerful but extremely complex. Here we give a new treatment that reduces the crushing process to a sequential combination of three “atomic” operations on a cell decomposition, all of which are simple to analyse. As an application, we generalise the crushing operation to the setting of non-orientable 3-manifolds, where we obtain a new practical and robust algorithm for non-orientable prime decomposition. We also apply our crushing techniques to the study of non-orientable minimal triangulations.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes

We investigate simplicial 3-manifolds, in particular 3-spheres, with few vertices such that the links of all vertices are combinatorially equivalent (equilinked 3-spheres), and, simple 3-manifolds, in particular 3-spheres, with few facets such that all facets are combinatorially equivalent (equifacetted 3-spheres).     

A locally regular heptagon–dodecahedron embedded in 3-space

We construct a polyhedral 2-manifold of genus 2 embedded in Euclidean 3-space, and hence oriented, built up of 12 planar (but nonconvex) heptagons, three meeting at each vertex, i.e., locally regular or equivelar. The polyhedron is face-minimal among all equivelar polyhedra of genus g≥2.It has a threefold symmetry axis and exists in two chiral versions.     

Crosscap numbers of 2-bridge knots

We present a practical algorithm to determine the minimal genus of non-orientable spanning surfaces for 2-bridge knots, called the crosscap numbers. We will exhibit a table of crosscap numbers of 2-bridge knots up to 12 crossings (all 362 of them).     

On the genus of the semidirect product of ℤ9 by ℤ3

We show that the non-commutative semidirect product Γ of ?₉ by ?₃ has orientable genus 4. In other words, some Cayley graph of Γ embeds in an orientable surface of genus 4 (Euler characteristic ?6), but no Cayley graph of Γ embeds in an orientable surface of genus less than 4 (Euler characteristic greater than ?6). We also show that some Cayley graph of Γ embeds in a (non-orientable) surface of Euler characteristic ?3, but no Cayley graph of Γ embeds in a surface of Euler characteristic greater than ?3. Γ is the first known example of a group whose orientable Euler characteristic and non-orientable Euler characteristic differ by more than 1. Our results also complete the determination of the orientable genus of each group of order less than 32.     

On the Generation of Oriented Matroids

We provide a multiple purpose algorithm for generating oriented matroids. An application disproves a conjecture of Grünbaum that every closed triangulated orientable 2-manifold can be embedded geometrically in R ³ , i.e., with flat triangles and without self-intersections. We can show in particular that there exists an infinite class of orientable triangulated closed 2-manifolds for each genus g \geq 6 that cannot be embedded geometrically in Euclidean 3-space. Our algorithm is interesting in its own right as a tool for many investigations in which oriented matroids play a key role. Received January 7, 1999, and in final form July 16, 1999.     

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.     

Collapses, products and LC manifolds

The quantum physicists Durhuus and Jonsson (1995) [9] introduced the class of “locally constructible” (LC) triangulated manifolds and showed that all the LC 2- and 3-manifolds are spheres. We show here that for each d>3 some LC d-manifolds are not spheres. We prove this result by studying how to collapse products of manifolds with one facet removed.     

Two Comments Concerning the Uniqueness of Prime Factorizations for 3-Manifolds

The proof of the uniqueness of prime factorizations of non-orientable3-manifolds appearing in Hempel's text is patched.