کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428983 | 686985 | 2013 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Density of straight-line 1-planar graph drawings Density of straight-line 1-planar graph drawings](/preview/png/428983.png)
A 1-planar drawing of a graph is such that each edge is crossed at most once. In 1997, Pach and Tóth showed that any 1-planar drawing with n vertices has at most 4n−84n−8 edges and that this bound is tight for n⩾12n⩾12. We show that, in fact, 1-planar drawings with n vertices have at most 4n−94n−9 edges, if we require that the edges are straight-line segments. We also prove that this bound is tight for infinitely many values of n⩾8n⩾8. Furthermore, we investigate the density of 1-planar straight-line drawings with additional constraints on the vertex positions. We show that 1-planar drawings of bipartite graphs whose vertices lie on two distinct horizontal layers have at most 1.5n−21.5n−2 edges, and we prove that 1-planar drawings such that all vertices lie on a circumference have at most 2.5n−42.5n−4 edges; both these bounds are also tight.
► New tight bounds on the number of edges of general straight-line 1-planar drawings of graphs.
► New tight bounds on the number of edges of 2-layer straight-line 1-planar drawings of graphs.
► New tight bounds on the number of edges of circular straight-line 1-planar drawings of graphs.
Journal: Information Processing Letters - Volume 113, Issue 7, 15 April 2013, Pages 236–240