This paper shows that a simple graph which can be cellularly embedded on so
me closed surface in such a way that the size of each face does not exceed
7 is upper embeddable. This settles one of two conjectures posed by Nedela
and Skoviera (1990, in "Topics in Combinatorics and Graph Theory," pp. 519-
529, Physica Verlag, Heidelberg). The other conjecture will be proved in a
sequel to this paper. (C) 2000 Academic Press.