A properly typeset version of this document is available in postscript and in pdf . However, the random graph model is not a very realistic model for databases, so it is useful to examine other structures. A map, or embedding of a graph into a surface of fixed genus, may be a better model of certain kinds of geometric databases. The proof is based on game strategies and keeping track of anchors.
G are simply connected regions called faces .
Maps are considered up to homeomorphisms of the surface taking vertices to vertices, edges to edges and faces to faces. Like graphs, maps with a finite number of edges can be given various combinatorial representations. The first two, g and d , relate two by two the four adjacent crosses of each edge, g along faces and d along vertices. The last one, t , relates pairs of crosses sharing an incidence between a face and a vertex. Now let us consider the vocabulary S 1 consisting of a set of constants and the binary relations G , D and T .