Two maps on one surface

DOI10.1002/1097-0118(200104)36:4%3C198::AID-JGT1006%3E3.0.CO;2-HMaRDI QIDQ2725321zbMATH OpenOpenAlexFDO

Authors C. Paul Bonnington, Dan S. Archdeacon

Publication date 16 April 2002

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/1097-0118(200104)36:4%3C198::aid-jgt1006%3E3.0.co;2-h

zbMATH Keywords

edge crossingsembeddingssurfacetorus

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

The authors consider simultaneous embeddings of two graphs on a surface. The problem is to find equivalent embeddings of the two given embeddings such that the total number of edge crossings is minimum. (No two edges in the same graph cross.) For the projective plane the problem is solved completely: The minimum number of crossings is the product of the lengths of the shortest noncontractible cycles in the dual graphs. Upper and lower bounds in the torus case are also presented, and the general case is briefly discussed.

Recommendations

• Two maps with large representativity on one surface
• On simultaneous planar graph embeddings
• Algorithms and Data Structures
• Crossing number of simultaneous embedding of two planar graphs with restriction
• Simultaneous Embedding with Two Bends per Edge in Polynomial Area

Cited in

(9)

• Shortest path embeddings of graphs on surfaces
• Double standard maps
• Crossing number additivity over edge cuts
• The crossing numbers of two-maps on orientable surfaces
• Crossing number of simultaneous embedding of two planar graphs with restriction
• Trading crossings for handles and crosscaps
• Two maps with large representativity on one surface
• Low-dimensional topology. Abstracts from the workshop held January 15--21, 2023
• Short topological decompositions of non-orientable surfaces

This page was built for publication: Two maps on one surface

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2725321)