Abstract

Title: Removing Even Crossings, Continued
Published: August 2006
Authors: Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovic
Abstract: In this paper we investigate how certain results related to the Hanani-Tutte theorem can be lifted to orientable surfaces of higher genus. We give a new simple, geometric proof that the weak Hanani-Tutte theorem is true for higher-genus surfaces. We extend the proof to prove that bipartite generalized thrackles in a surface S can be embedded in S.

We also show that a result of Pach and Tòth that allows the redrawing of a graph removing intersections on even edges remains true on higher-genus surfaces. As a consequence, we can conclude that crS(G), the crossing number of the graph G on surface S, is bounded by 2 ocrS(G), where ocrS(G) is the odd crossing number of G on surface S.

Finally, we begin an investigation of optimal crossing configurations for which cr is linearly bounded in ocr.
Full Paper: [postscript, pdf]