Removing even crossings on surfaces |
| |
Authors: | Michael J Pelsmajer Marcus Schaefer Daniel tefankovi
|
| |
Institution: | aDepartment of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, USA;bDepartment of Computer Science, DePaul University, Chicago, IL 60604, USA;cComputer Science Department, University of Rochester, Rochester, NY 14627-0226, USA |
| |
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 S can be embedded on S. 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 , the crossing number of a graph G on surface S, is bounded by , where is the odd crossing number of G on surface S. Finally, we prove that whenever , for any surface S. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|