کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647258 | 1632411 | 2014 | 6 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 331, 28 September 2014, Pages 83–88