Connection Graphs for 3-Triangulations of Toroids

Abstract

Although it is possible to 3-triangulate all convex polyhedra, this is not the case for certain non-convex ones. If 3-triangulation of some polyhedron is possible, then a connection graph is introduced in such a way that convex pieces of that polyhedron are represented by graph nodes.

A method for constructing a polyhedron $P$ based on a given connected non-orientable graph is given and the properties of $P$ are investigated. The algorithms for computing the numbers of vertices, edges, faces and handles of $P$ are also given.