Approximating the rectilinear crossing number

Fox, Jacob and Pach, János and Suk, Andrew (2019) Approximating the rectilinear crossing number. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 81. pp. 45-53. ISSN 0925-7721

Preview

Text 160603753.pdf Available under License Creative Commons Attribution. Download (228kB) | Preview

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) over bar (G), is the minimum number of pairs of crossing edges in any straight-line drawing of G. Determining or estimating (cr) over bar (G) appears to be a difficult problem, and deciding if (cr) over bar (G) <= k is known to be NP-hard. In fact, the asymptotic behavior of (cr) over bar (K-n) is still unknown. In this paper, we present a deterministic n(2+o(1))-time algorithm that finds a straight-line drawing of any n-vertex graph G with ((cr) over barG)+ 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) over bar (G) pairs of crossing edges. (C) 2019 Elsevier B.V. All rights reserved.

Actions (login required)

Edit Item