Historically, polyhedral maps on surfaces made their first appearance as convex polyhedra. The famous Kepler-Poinsot (star) polyhedra marked the first occurrence of maps on orientable surfaces of higher genus (namely 4), and started the branch of topology dealing with regular maps. Further impetus to the subject came from the theory of automorphic functions and from the Four-Color-Problem (Coxeter and Moser [[CM80]], Barnette [[Bar83]]).