Two maps on one surface

Two embeddings of a graph in a surface S are said to be "equivalent" if the y are identical under an homeomorphism of S that is orientation-preserving for orientable S. Two graphs cellularly embedded simultaneously in S are sa id to be "jointly embedded" if the only points of intersection involve an e dge of one graph transversally crossing an edge of the other. The problem i s to find equivalent embeddings of the two graphs that minimize the number of these edge-crossings; this minimum we call the "joint crossing number" o f the two graphs. in this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective p lane. Furthermore, we give upper and lower bounds when the surface is the t orus, which in many cases give an exact answer. In particular, we give a co nstruction for re-embedding (equivalently) the graphs in the torus so that the number of crossings is best possible up to a constant factor. Finally, we show that if one of the embeddings is replaced by its "mirror image," th en the joint crossing number can decrease, but not by more than 6.066%, (C) 2001 John Wiley gi Sons,Inc.