首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Removing even crossings on surfaces
Authors:Michael J Pelsmajer  Marcus Schaefer  Daniel &#x;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 View the MathML source, the crossing number of a graph G on surface S, is bounded by View the MathML source, where View the MathML source is the odd crossing number of G on surface S. Finally, we prove that View the MathML source whenever View the MathML source, for any surface S.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号