The great dodecahedron is a non-convex regular polyhedron bounded by 12 pentagonal faces, crossing each other, arranged in a star-shaped manner around each of its 12 vertices (see the Wikipedia page for a picture.) From a topological point of view, the abstract surface that you get if you glue the faces along the corresponding sides is a compact orientable surface; hence it is homeomorphic to a sphere with some number of handles. It is easy to check that it has genus 4. (You can also see it as a 3-sheeted Riemann surface with 12 branch-points.)
Thus it is possible to draw, on the surface of a 4-holed torus, a graph consisting of 12 vertices and 30 edges that subdivides the surface into 12 pentagonal regions, with 5 such regions meeting at each vertex. To put it more concisely: there exists a sort of 4-holed polyhedron which is regular in at least a topological (or, if you prefer, combinatorial) sense and whose Schläfli symbol would be {5 5}.
I was actually able to draw such a picture, but all I see is a tangle of lines twisting and wrapping around in all directions. My picture has no obvious symmetry. Is it possible to embed this object in ordinary 3-space without self-intersections, but with, let's say, at least an axis of 5-fold rotation? (Unfortunately, I suspect the answer is "no".) Or is it possible to at least make sure that there is a group of easily described transformations that coincides, at least partially, with the abstract symmetry group of the configuration (which has order 120)?