On the Density of Nonsimple 3Planar GraphsBekos, Michael A. and Kaufmann, Michael and Raftopoulou, Chrysanthi N. (2016) On the Density of Nonsimple 3Planar Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 344356(Official URL: http://dx.doi.org/10.1007/9783319501062_27). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_27
AbstractA kplanar graph is a graph that can be drawn in the plane such that every edge is crossed at most k times. For k≤4, Pach and Tóth [20] proved a bound of (k+3)(n−2) on the total number of edges of a kplanar graph, which is tight for k=1,2. For k=3, the bound of 6n−12 has been improved to 11/2n−11 in [19] and has been shown to be optimal up to an additive constant for simple graphs. In this paper, we prove that the bound of 11/2n−11 edges also holds for nonsimple 3planar graphs that admit drawings in which nonhomotopic parallel edges and selfloops are allowed. Based on this result, a characterization of optimal 3planar graphs (that is, 3planar graphs with n vertices and exactly 11/2n−11 edges) might be possible, as to the best of our knowledge the densest known simple 3planar is not known to be optimal.
Actions (login required)
