Some questions on toroidal graphs The complete graph $K_4$ is planar, and like every planar graph it is also embeddable into the torus.
a) Why does $K_4$ count as a triangulation of the sphere, but not of the torus?
b) What's the name of graphs that are toroidal, but not planar?
c) Is there a criterion for toroidal graphs comparable to Kuratowski's for planar graphs?
 A: You want the book Topological Graph Theory by Gross and Tucker. 
Note that $K_7$ can be imbedded in the torus, page 137. So, my guess for part (a) is that you cannot draw $K_4$ on the torus in such a way that each edge triple making a triangle in the graph actually bounds a simply connected region on the surface. 
(b) called genus one.
(c) not sure. Note complete bipartite $K_{4,4}$ and $K_{3,6}$ are genus one, page 211, Thm 4.5.3, Ringel (1965) 
A: An embedding is triangular if each face is a triangle. For the embedding of $K_4$ you have in mind, one face is not bounded by a triangle - the "outside" face.
Note that for surfaces other than the sphere, it is required that each face be homeomorphic to a disc, i.e., the embedding must be cellular. The graphs will cellular embeddings in a given surface form a minor-closed class, so by the Roberston-Seymour theorem there is a finite class of forbidden minors and hence we do have a good analog of Kuratowski's theorem. Note though, that finite does not mean small.
