We give coordinate-minimal geometric realizations in general position for all 865 vertex-minimal triangulations of the orientable surface of genus 2 in the 4x4x4-cube.

In 1890, Heawood [11] proved that a triangulation of a (closed) surface M of Euler characteristic chi(M) has at least

n ≥ 1/2(7+sqrt(49-24*chi(M)))

vertices. With the exception of the orientable surface of genus 2, the Klein bottle, and the non-orientable surface of genus 3 this bound is tight, as was shown only much later by Ringel [20] for non-orientable surfaces and by Jungerman and Ringel [16] for orientable surfaces. In the three exceptional cases one extra vertex has to be added, respectively, to allow for triangulations. For the orientable surface of genus 2 this was proved by Huneke [15]. Hence, vertex-minimal triangulations of the orientable surface of genus 2 have 10 vertices.

A complete enumeration of all 42426 triangulated surfaces with 10 vertices was obtained in [17]; see [18] for a list of facets (in mixed lexicographic format as well as in lexicographic format) and [22] for an isomorphism free lexicographic enumeration of the triangulations with up to 12 vertices. In particular, there are exactly 865 combinatorially distinct vertex-minimal 10-vertex triangulations of the orientable surface of genus 2.

By Steinitz' theorem (cf. [23, Ch. 4]), every triangulated 2-sphere
is realizable as the boundary complex of a convex 3-dimensional polytope.
For orientable surfaces of genus g ≥ 1 Grünbaum [10, Ch. 13.2] asked
whether triangulations of these surfaces can always be
*realized geometrically as polyhedra* in **R**^{3},
i.e., with straight edges, flat triangles, and without self intersections?
In general, the answer turned out to be "*No*":
Bokowski and Guedes de Oliveira [5] showed that there is a non-realizable
triangulation of the orientable surface of genus g = 6. Recently, Schewe [21]
extended this result and proved that there are non-realizable triangulations
for all orientable surfaces of genus g ≥ 5.
For surfaces of genus 1 ≤ g ≤ 4 the problem remains open.

Geometric realizations for several examples of triangulated orientable surfaces of genus 2, 3, and 4 with respective minimal numbers of vertices 10, 10, and 11 were constructed by Bokowski and Brehm [3], [4] and Brehm [7], [8]. A first polyhedron of genus 2 with 10 vertices was obtained by Brehm in [7] from a polyhedron of genus 3 with 10 vertices by closing one of the holes.

The realizability problem for triangulated surfaces is decidable
(cf. Bokowski [1] and Bokowski and Sturmfels [6, Ch. VIII]), but there is *no*
deterministic algorithm known that would solve the realization problem
for instances with as few as, say, 10 vertices in reasonable time.

By *random realization*, geometric realizations in the 32768x32768x32768-cube
were obtained by Lutz [17] for 864 of the 865 examples of vertex-minimal 10-vertex
triangulations of the orientable surface of genus 2.
A realization of the remaining example was constructed by Bokowski [2].

**Theorem (Bokowski and Lutz, cf. [2], [17]):**
All 865 vertex-minimal 10-vertex triangulations of the orientable surface
of genus 2 can be realized geometrically in **R**^{3}.

In fact, all these examples have realizations with small coordinates.

**Theorem:**
All 865 vertex-minimal 10-vertex triangulations of the orientable surface
of genus 2 have realizations in general position in the 4x4x4-cube, but
cannot be realized in general position in the 3x3x3-cube.

Our realization algorithm for *general position realizations with small coordinates*
is a variant of the *isomorph-free exhaustive generation* as described by McKay [19]
for classes of objects with an inductive construction process. In our case,
we generate sets of increasing size s with up to 10 points with integer coordinates
in general position in the nxnxn-cube, which allow realizations of at least one induced subcomplex
with s vertices of a given triangulated orientable surface.

This realization algorithm can easily be adapted to also obtain *proper realizations*,
i.e., realizations that do not have coplanar neighboring triangles, but which not necessarily
need to be in general position (and which therefore might be of even smaller size).
Still more general, realizations with coplanar neighboring triangles can be produced as well.
This way, for example, we found realizations of triangulations of the torus
in the 2x2x2-cube; see [14]. Realizations with minimal coordinates were also found
for 17 of the 20 vertex-minimal triangulations of the orientable surface of genus 3 [12].
Moreover, it was shown in [13] that, in fact, all vertex-minimal triangulations
of the orientable surfaces of genus 1 ≤ g ≤ 4 are realizable.

The six displayed examples Polyhedron_2_10_11909 to Polyhedron_2_10_36618 were selected from the collection of the 865 general position realizations in the 4x4x4-cube for their clearly visible holes. The numbers 11909 to 36618 indicate the positions of the examples in the catalog of the 42426 triangulated surfaces with 10 vertices in mixed lexicographic format from [18]. Obj-files for all the 865 examples can be found in the archive Polyhedra_Genus-2_Vertices-10_Format-obj.tar.gz below.

Of the 865 examples, 789 have only trivial combinatorial symmetry,
61 examples have **Z**_{2}-symmetry, and 7 have **Z**_{3}-symmetry.
Further, there are 2 with **Z**_{4}-, 1 with **Z**_{8}-, and
4 with **Z**_{2}x**Z**_{2}-symmetry.
The example 41348 has the largest symmetry group <2,2|2>
of order 16 (with the group name in the notation of Coxeter and Moser [9, p. 134]).
The symmetry groups of the examples are contained in the archive
Polyhedra_Genus-2_Vertices-10_Format-other.tar.gz.

In general, the geometric symmetry group of a polyhedral surface
can be smaller than its combinatorial symmetry group. For example,
the geometric symmetry group of a polyhedron of genus 3 with 10
vertices is of order at most 4 [8], while there is an example
with combinatorial symmetry group A_{4} and another
with **Z**_{7}x**Z**_{3}; see [3] and [12].
It is not known which of the combinatorial symmetries of
the 865 examples of genus 2 with 10 vertices are realizable geometrically.

Acknowledgement: The first and the third author were supported by the DFG Research Center MATHEON "Mathematics for Key Technologies", Berlin, the second author was supported by the DFG Research Group "Polyhedral Surfaces", Berlin.

Keywords | triangulated surface; polyhedral realization; small coordinates | |

MSC-2000 Classification | 52B70 (57Q15) | |

Zentralblatt No. | 05264904 |

- J. Bokowski:
*Effective methods in computational synthetic geometry*, in J. Richter-Gebert and D. Wang (Eds.): Automated Deduction in Geometry, Proc. 3rd Internat. Workshop (ADG 2000), Zürich, 2000, Lecture Notes in Computer Science 2061, Springer-Verlag (2001), 175-192. - J. Bokowski:
*On heuristic methods for finding realizations of surfaces*, Preprint, 6 pages, 2006, to appear in Discrete Differential Geometry (A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. M. Ziegler, eds.), Oberwolfach Seminars, Birkhäuser, Basel. - J. Bokowski and U. Brehm:
*A new polyhedron of genus 3 with 10 vertices*, in K. Böröczky and G. Fejes Tóth (Eds.): Intuitive Geometry, Internat. Conf. on Intuitive Geometry, Siófok, Hungary, 1985, Colloquia Mathematica Societatis János Bolyai 48, North-Holland (1987), 105-116. - J. Bokowski and U. Brehm:
*A polyhedron of genus 4 with minimal number of vertices and maximal symmetry*, Geom. Dedicata**29**(1989), 53-64. - J. Bokowski and A. Guedes de Oliveira:
*On the generation of oriented matroids*, Discrete Comput. Geom.**24**(2000), 197-208. - J. Bokowski and B. Sturmfels: Computational Synthetic Geometry, Lecture Notes in Mathematics 1355, Springer-Verlag (1989).
- U. Brehm:
*Polyeder mit zehn Ecken vom Geschlecht drei*, Geom. Dedicata**11**(1981), 119-124. - U. Brehm:
*A maximally symmetric polyhedron of genus 3 with 10 vertices*, Mathematika**34**(1987), 237-242. - H. S. M. Coxeter and W. O. J. Moser: Generators and Relations for Discrete Groups, Ergebnisse der Mathematik und ihrer Grenzgebiete 14, Springer-Verlag (1957; fourth edition, 1980).
- B. Grünbaum: Convex Polytopes, Pure and Applied Mathematics 16, Interscience Publishers (1967; second edition, V. Kaibel, V. Klee, and G. M. Ziegler (Eds.), Graduate Texts in Mathematics 221, Springer-Verlag, 2003).
- P. J. Heawood:
*Map-colour theorem*, Quart. J. Pure Appl. Math.**24**(1890), 332-338. - S. Hougardy, F. H. Lutz, and M. Zelke:
*Polyhedra of genus 3 with 10 vertices and minimal coordinates*, Electronic Geometry Models (2007), 2006.02.001, http://www.eg-models.de/2006.02.001. - S. Hougardy, F. H. Lutz, and M. Zelke:
*Surface realization with the intersection edge functional*, Preprint, 19 pages, 2006, http://arxiv.org/abs/math.MG/0608538. - S. Hougardy, F. H. Lutz, and M. Zelke:
*Polyhedral tori with minimal coordinates*, in preparation. - J. P. Huneke:
*A minimum-vertex triangulation*, J. Comb. Theory, Ser. B**24**(1978), 258-266. - M. Jungerman and G. Ringel:
*Minimal triangulations on orientable surfaces*, Acta Math.**145**(1980), 121-154. - F. H. Lutz:
*Enumeration and random realization of triangulated surfaces*, Preprint, 18 pages, 2006, to appear in Discrete Differential Geometry (A. I. Bobenko, J. M. Sullivan, P. Schröder, and G. M. Ziegler, eds.), Oberwolfach Seminars, Birkhäuser, Basel, http://arxiv.org/abs/math.CO/0506316. - F. H. Lutz:
*The Manifold Page*, 1999-2007, http://www.math.tu-berlin.de/diskregeom/stellar/. - B. D. McKay:
*Isomorph-free exhaustive generation*, J. Algorithms**26**(1998), 306-324. - G. Ringel:
*Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann*, Math. Ann.**130**(1955), 317-326. - L. Schewe:
*Satisfiability Problems in Discrete Geometry*, Dissertation, Technische Universität Darmstadt, 101 pages, 2007. - T. Sulanke and F. H. Lutz:
*Isomorphism free lexicographic enumeration of triangulated surfaces and 3-manifolds*, Preprint, 20 pages, 2006, http://arxiv.org/abs/math.CO/0610022. - G. M. Ziegler: Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag (1995; revised edition, 1998).

- Master File: Polyhedron_2_10_36618.jvx
- Master File: Polyhedron_2_10_27198.jvx
- Master File: Polyhedron_2_10_22811.jvx
- Master File: Polyhedron_2_10_20332.jvx
- Master File: Polyhedron_2_10_14684.jvx
- Master File: Polyhedron_2_10_11909.jvx
- Applet File: Polyhedron_2_10_36618.jvx
- Applet File: Polyhedron_2_10_27198.jvx
- Applet File: Polyhedron_2_10_22811.jvx
- Applet File: Polyhedron_2_10_20332.jvx
- Applet File: Polyhedron_2_10_14684.jvx
- Applet File: Polyhedron_2_10_11909.jvx
- Preview: Polyhedron_2_10_36618.gif
- Preview: Polyhedron_2_10_27198.gif
- Preview: Polyhedron_2_10_22811.gif
- Preview: Polyhedron_2_10_20332.gif
- Preview: Polyhedron_2_10_14684.gif
- Preview: Polyhedron_2_10_11909.gif
- Other: Polyhedra_Genus-2_Vertices-10_Format-obj.tar.gz
- Other: Polyhedra_Genus-2_Vertices-10_Format-other.tar.gz

Submitted: Fri Aug 5 16:30:33 MET DST 2005.

Revised: Wed Sep 6 12:59:00 MET DST 2006, Mon Mar 12 15:34:00 MET DST 2007.

Accepted: Tue Mar 20 12:07:00 MET 2007.

Humboldt-Universität zu BerlinFrank H. Lutz

Institut für Informatik

Unter den Linden 6

10099 Berlin

Germany

hougardy@informatik.hu-berlin.de

http://www.informatik.hu-berlin.de/~hougardy/

Technische Universität BerlinMariano Zelke

Fakultät II - Mathematik und Naturwissenschaften

Institut für Mathematik, Sekr. MA 3-2

Straße des 17. Juni 136

10623 Berlin

Germany

lutz@math.tu-berlin.de

http://www.math.tu-berlin.de/~lutz

Humboldt-Universität zu Berlin

Institut für Informatik

Unter den Linden 6

10099 Berlin

Germany

zelke@informatik.hu-berlin.de

http://www.informatik.hu-berlin.de/~zelke/