Two maps on one surface

Dan Archdeacon, C. Paul Bonnington

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)

Abstract

Two embeddings of a graph in a surface S are said to be "equivalent" if they are identical under an homeomorphism of S that is orientation-preserving for orientable S. Two graphs cellularly embedded simultaneously in S are said to be "jointly embedded" if the only points of intersection involve an edge of one graph transversally crossing an edge of the other. The problem is to find equivalent embeddings of the two graphs that minimize the number of these edge-crossings; this minimum we call the "joint crossing number" of the two graphs. In this paper, we calculate the exact value for the joint crossing number for two graphs simultaneously embedded in the projective plane. Furthermore, we give upper and lower bounds when the surface is the torus, which in many cases give an exact answer. In particular, we give a construction 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," then the joint crossing number can decrease, but not by more than 6.066%

Original languageEnglish
Pages (from-to)198-216
Number of pages19
JournalJournal of Graph Theory
Volume36
Issue number4
DOIs
Publication statusPublished - 1 Jan 2001
Externally publishedYes

Keywords

  • Crossings
  • Toroidal maps

Cite this