On 3-Layer Crossings and Pseudo Arrangements

. Let G = (V0 ; V1 ; V2 ; E) be a 3-layer graph. The 3-layer drawings of G in which V0 , V1 , and V2 are placed on 3 parallel lines and each edge in E is drawn using one straight line segment, are studied. A generalization of the linear arrangement problem which we call the 3-layer pseudo linear arrangement problem is introduced, and it is shown to be closely related to the 3-layer crossing number. In particular, we show that the 3-layer crossing number of G plus the sum of the square of degrees asymptotically has the same order of magnitude as the optimal solution to the 3-layer linear arrangement problem. Consequently, when G satisfies certain (reasonable) assumptions, we derive the first polynomial time approximation algorithm to compute the 3-layer crossing number within a multiplicative factor of O(log n) from the optimal. 1 Introduction The planar crossing number problem is the problem of placing the vertices of a graph in the plane and drawing the edges with curves, to minimize..