Approximating the Rectilinear Crossing Number

Fox, 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. 413-426(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_32).

Full text not available from this repository.

Abstract

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line 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 straight-line drawing of G. Determining or estimating cr¯(G) appears to be a difficult problem, and deciding if cr¯(G)≤k is known to be NP-hard. 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 straight-line drawing of any n-vertex graph G with cr¯(G)+o(n^4) pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense n-vertex graph G, one can efficiently find a straight-line drawing of G with (1+o(1))cr¯(G) pairs of crossing edges.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.420 Crossings P Styles > P.720 Straight-line
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1559

Actions (login required)

View Item