On 3-Layer Crossings and Pseudo Arrangements
Shahrokhi, Farhad and Vrt'o, Imrich (1999) On 3-Layer Crossings and Pseudo Arrangements. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 225-231 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_23).
Full text not available from this repository.
Let G = (V_0, V_1, V_2, E) be a 3-layer drawings of G in which V_0, V_1, and V_2 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 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.
Repository Staff Only: item control page