ON THE FACE TOUCHING NUMBER

In a 3-connected plane graph, each pair of faces meet at at most eithe r a vertex or an edge. Zha considered 3-connected graphs embedded on t he projective plane, torus, and Klein bottle, showing that they meet a t at most two, at most four, and at most four vertices or edges, respe ctively, and demonstrated graphs that showed that these bounds were be st possible. He asked the question on what the maximum number of times two faces can meet on a general surface. This paper solves that probl em, showing that two faces of a graph embedded on a non-planar surface of Euler characteristic epsilon meet at most 4-2 epsilon times. The p roof uses the Discharging Method, and seems to be the first applicatio n of this method to a problem which is wholly about graph embeddings. Also, graphs are demonstrated to show that this result is best possibl e. (C) 1996 John Wiley & Sons, Inc.