Euler’s formula for a polyhedron with V vertices, F faces and E edges and genus g states that V + F − E = 2(1 − g). Cayley formulated a similar expression for the four Kepler-Poinsot polyhedra: bV + aF − E = 2c, using the densities a, b and c of respectively the faces, the vertices and the polyhedron itself. We conjecture both should be united as bV + aF − E = 2c(1 &minus g), or, more generally, for Archimedean polyhedra with V_j vertices and F_i faces of a given type and densities b_j and a_i respectively, as ∑b_jV_j + ∑a_iF_i &minus EM = 2c(1 − g). We consider examples that support our case, but a more important aspect of this paper is perhaps the suggestion of considering higher genus Kepler-Poinsot polyhedra. Some are unusual cases inspired by S. Gott’s pseudo-polyhedra with adjacent faces in the same plane, while other types of these star polyhedra may be attractive from an artistic point of view. Escher was interested in star polyhedra and in infinite tessellations, and the polyhedra proposed in the present paper combine both topics.