کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647258 1632411 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex geometric (k+2)(k+2)-quasiplanar representations of semi-bar kk-visibility graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Convex geometric (k+2)(k+2)-quasiplanar representations of semi-bar kk-visibility graphs
چکیده انگلیسی

Semi-bar kk-visibility graphs are graphs for which vertices can be drawn as horizontal segments with left endpoints on the yy-axis (semi-bars) and edges can be drawn as vertical segments (sightlines) so that two semi-bars are visible to each other if and only if there is a sightline which intersects them and at most kk other semi-bars. Cyclic semi-bar kk-visibility graphs are graphs for which vertices can be drawn as segments with one endpoint at the origin (semi-bars) and edges can be drawn as arcs of circles centered at the origin (sightlines) so that two semi-bars are visible to each other if and only if there is a sightline which intersects them and at most kk other semi-bars. We show that every semi-bar or cyclic semi-bar kk-visibility graph can be represented in the plane with vertices drawn as points in convex position and edges drawn as segments so that there are no k+2k+2 pairwise crossing edges. Furthermore, we prove that the class of graphs having cyclic semi-bar kk-visibility representations with semi-bars of different lengths is the same as the class of (2k+2)(2k+2)-degenerate graphs that can be represented in the plane with vertices drawn as points in convex position and edges drawn as segments so that there are no k+2k+2 pairwise crossing edges and so that adding any edge would result in k+2k+2 pairwise crossing edges.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 331, 28 September 2014, Pages 83–88
نویسندگان
, , ,