کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654412 1632818 2009 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Removing even crossings on surfaces
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Removing even crossings on surfaces
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 30, Issue 7, October 2009, Pages 1704–1717
نویسندگان
, , ,