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, Perugia, Italy , pp. 406-418 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_38).

Full text not available from this repository.

Abstract

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
ID Code:470

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia and I. G. Tollis, Graph Drawing: Algorithms for Visualization of Graphs, Prentice Hall (1999).

V. Dujmovic and S. Whitesides, An efficient fixed parameter tractable algorithm for 1-sided crossing minimization, Graph Drawing 2002, Lecture Notes in Computer Science, 2528, Springer-Verlag, Berlin (2002) 118-129.

P. Eades and N. C. Wormald, Edge crossing in drawing bipartite graphs, Algorithmica, 11 (1994) 379-403.

M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods, 4 (1983) 312-316.

F. Harary and A. J. Schwenk, Trees with Hamiltonian square, Mathematics, 18(1971) 138-140.

F. Harary and A. J. Schwenk, A new crossing number for bipartite graphs, Utilitas Math., 1 (1972) 203-209.

M. Jünger and P. Mutzel, 2-layer straight line crossing minimization: performance of exact and heuristic algorithms, J. Graph Algorithms and Applications, 1 (1997) 1-25.

X. Y-Li and M. F. Sallmann, New bounds on the barycenter heuristic for bipartite drawing, Information Processing Letters, 82 (2002) 293-298.

E. Mäkinen, Experiments on drawing 2-level hierarchical graphs, International Journal of Computer Mathematics, 36 (1990) 175-181.

X. Munoz, W. Unger and I. Vrt'o, One sided crossing minimization is NP-hard for sparse graphs, Graph Drawing 2001, Lecture Notes in Computer Science, 2265, Springer-Verlag, Berlin (2002) 115-123.

C. Sechen, VLSI Placement and Global Routing Using Simulated Annealing, Kluwer, Dortrecht (1988).

K. Sugiyama, S. Tagawa and M. Toda, Methods for visual understanding of hierarchical system structures, IEEE Transactions on Systems, Man, and Cybernetics, 11 (1981) 109-125.

A. Yamaguchi and A. Sugimoto, An approximation algorithm for the two-layered graph drawing problem, In 5th Annual Intl. Conf. on Computing and Combinatorics, Lecture Notes in Computer Science, 1627, Springer-Verlag, Berlin (1999) 81-91.