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 {c uv , c vu } over all node pairs u,v εV, where c uv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering.
Chapter PDF
Similar content being viewed by others
References
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)
Dujmović, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 118–129. Springer, Heidelberg (2002)
Eades, P., Wormald, N.C.: Edge crossing in drawing bipartite graphs. Algorithmica 11, 379–403 (1994)
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods 4, 312–316 (1983)
Harary, F., Schwenk, A.J.: Trees with Hamiltonian square. Mathematiks 18, 138–140 (1971)
Harary, F., Schwenk, A.J.: A new crossing number for bipartite graphs. Utilitas Math. 1, 203–209 (1972)
Jünger, M., Mutzel, P.: 2-layer straight line crossing minimization: performance of exact and heuristic algorithms. J. Graph Algorithms and Applications 1, 1–25 (1997)
Li, X.Y., Sallmann, M.F.: New bounds on the barycenter heuristic for bipartite drawing. Information Processing Letters 82, 293–298 (2002)
Mäkinen, E.: Experiments on drawing 2-level hierarchical graphs. International Journal of Computer Mathematics 36, 175–181 (1990)
Muñoz, X., Unger, W., Vrt’o, I.: One sided crossing minimization is NP-hard for sparse graphs. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 115–123. Springer, Heidelberg (2002)
Sechen, C.: VLSI Placement and Global Routing Using Simulated Annealing. Kluwer, Dordrecht (1988)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11, 109–125 (1981)
Yamaguchi, A., Sugimoto, A.: An approximation algorithm for the two-layered graph drawing problem. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 81–91. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nagamochi, H. (2004). An Improved Approximation to the One-Sided Bilayer Drawing. In: Liotta, G. (eds) Graph Drawing. GD 2003. Lecture Notes in Computer Science, vol 2912. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24595-7_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-24595-7_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20831-0
Online ISBN: 978-3-540-24595-7
eBook Packages: Springer Book Archive