Approximating the Rectilinear Crossing NumberFox, Jacob and Pach, János and Suk, Andrew (2016) Approximating the Rectilinear Crossing Number. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 413426(Official URL: http://dx.doi.org/10.1007/9783319501062_32). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_32
AbstractA straightline drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straightline segment connecting the corresponding two points. The rectilinear crossing number of a graph G,cr(G), is the minimum number of pairs of crossing edges in any straightline drawing of G. Determining or estimating cr¯(G) appears to be a difficult problem, and deciding if cr¯(G)≤k is known to be NPhard. In fact, the asymptotic behavior of cr¯(Kn) is still unknown. In this paper, we present a deterministic n2+o(1)time algorithm that finds a straightline drawing of any nvertex graph G with cr¯(G)+o(n^4) pairs of crossing edges. Together with the wellknown Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense nvertex graph G, one can efficiently find a straightline drawing of G with (1+o(1))cr¯(G) pairs of crossing edges.
Actions (login required)
