An Improved Approximation to the One-Sided Bilayer Drawing

Nagamochi, Hiroshi (2004) An Improved Approximation to the One-Sided Bilayer Drawing. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 406-418(Official URL:

Full text not available from this repository.


Given a bipartite graph G=(V,W,E), a bilayer drawing consists of placing nodes in the first vertex set V on a straight line L_1 and placing nodes in the second vertex set W on a parallel line L_2. The one-sided crossing minimization problem asks to find an ordering of nodes in V to be placed on L_1 so that the number of arc crossings is minimized. In this paper, we prove that there always exits a solution whose crossing number is at most 1.4664 times of a well-known lower bound that is obtained by summing up min{c_{uv}, c_{vu}} over all node pairs u, v \epsilon V, where c_uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_38
Classifications: G Algorithms and Complexity > G.420 Crossings
M Methods > M.500 Layered
P Styles > P.480 Layered

Actions (login required)

View Item View Item