Title: | Removing Even Crossings, Continued |
Authors: | Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič |
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] |