On 3Layer Crossings and Pseudo ArrangementsShahrokhi, Farhad and Vrt'o, Imrich (1999) On 3Layer Crossings and Pseudo Arrangements. In: Graph Drawing 7th International Symposium, GD’99, September 1519, 1999 , pp. 225231(Official URL: http://dx.doi.org/10.1007/3540466487_23). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540466487_23
AbstractLet G = (V_0, V_1, V_2, E) be a 3layer 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 3layer pseudo linear arrangement problem is introduced, and it is shown to be closely related to the 3layer 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 3layer linear arrangement problem. Consequently, when G satisfies certain (reasonable) assumptions, we derive the first polynomial time approximation algorithm to compute the 3layer crossing number within a multiplicative factor of O(log n) from the optimal.
Actions (login required)
