Name
Abstract | ||
|---|---|---|
Two embeddings of a graph in a surface S are said to be"equivalent" if they are identical under an homeomorphism ofS that is orientation-preserving for orientable S.Two graphs cellularly embedded simultaneously in S are saidto be "jointly embedded" if the only points of intersection involvean edge of one graph transversally crossing an edge of the other.The problem is to find equivalent embeddings of the two graphs thatminimize the number of these edge-crossings; this minimum we callthe "joint crossing number" of the two graphs. In this paper, wecalculate the exact value for the joint crossing number for twographs simultaneously embedded in the projective plane.Furthermore, we give upper and lower bounds when the surface is thetorus, which in many cases give an exact answer. In particular, wegive a construction for re-embedding (equivalently) the graphs inthe torus so that the number of crossings is best possible up to aconstant factor. Finally, we show that if one of the embeddings isreplaced by its "mirror image," then the joint crossing number candecrease, but not by more than 6.066%. © 2001 John Wiley &Sons, Inc. J Graph Theory 36: 198216, 2001 |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1002/1097-0118(200104)36:4<>1.0.CO;2-O | Journal of Graph Theory |
Keywords | Field | DocType |
lower bound,projective plane | Topology,Discrete mathematics,Indifference graph,Combinatorics,Crossing number (graph theory),Chordal graph,Book embedding,Toroidal graph,Pathwidth,1-planar graph,Topological graph theory,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 4 | 0364-9024 |
Citations | PageRank | References |
2 | 0.42 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan Archdeacon | 1 | 277 | 50.72 |
| C. Paul Bonnington | 2 | 100 | 19.95 |