Article ID Journal Published Year Pages File Type
4654412 European Journal of Combinatorics 2009 14 Pages PDF
Abstract

In this paper we investigate how certain results related to the Hanani–Tutte theorem can be extended from the plane to surfaces. We give a simple topological proof that the weak Hanani–Tutte theorem is true on arbitrary surfaces, both orientable and non-orientable. We apply these results and the proof techniques to obtain new and old results about generalized thrackles, including that every bipartite generalized thrackle on a surface SS can be embedded on SS. We also extend to arbitrary surfaces a result of Pach and Tóth that allows the redrawing of a graph so as to remove all crossings with even edges. From this we can conclude that crS(G), the crossing number   of a graph GG on surface SS, is bounded by 2ocrS(G)2, where ocrS(G) is the odd crossing number   of GG on surface SS. Finally, we prove that ocrS(G)=crS(G) whenever ocrS(G)≤2, for any surface SS.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,