کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647622 | 1342363 | 2013 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Proper 1-immersions of graphs triangulating the plane
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper we study what planar graphs are “rigid” enough such that they can not be drawn on the plane with few (1, 2, or 3) crossings per edge. A graph drawn on the plane is kk-immersed in the plane if each edge is crossed by at most kk other edges. By a proper kk-immersion of a graph we mean a kk-immersion of the graph in the plane such that there is at least one crossing point. We give a characterization (in terms of forbidden subgraphs) of 4-connected graphs which triangulate the plane and have a proper 1-immersion. We show that every planar graph has a proper 3-immersion.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 23, 6 December 2013, Pages 2673–2686
Journal: Discrete Mathematics - Volume 313, Issue 23, 6 December 2013, Pages 2673–2686
نویسندگان
Vladimir P. Korzhik,