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 , 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_23
Classifications: M Methods > M.500 Layered
G Algorithms and Complexity > G.700 Layering
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
URI: http://gdea.informatik.uni-koeln.de/id/eprint/323

Actions (login required)

View Item View Item