کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647622 1342363 2013 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Proper 1-immersions of graphs triangulating the plane
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Proper 1-immersions of graphs triangulating the plane
چکیده انگلیسی

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
نویسندگان
,