Abstract
This paper studies 2-layer RAC drawings of bipartite graphs. The contribution is as follows: (i) We prove that the problem of computing the maximum 2-layer RAC subgraph is NP-hard even when the vertex ordering on one layer is fixed; this extends a previous NP-hardness result that allows the vertices to be permuted on each layer. (ii) We describe a 3-approximation algorithm for the maximum 2-layer RAC subgraph problem when the vertex ordering on each layer is not fixed, and a heuristic for the case that the vertex ordering on one of the layers is fixed. (iii) We present an experimental study that evaluates the effectiveness of the proposed approaches.
Work supported in part by MIUR of Italy under project AlgoDEEP prot. 2008TFBWL4.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angelini, P., Cittadini, L., Di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the perspectives opened by right angle crossing drawings. JGAA 15(1), 53–78 (2011)
Arikushi, K., Fulek, R., Keszegh, B., Morić, F., Tóth, C.D.: Graphs that Admit Right Angle Crossing Drawings. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 135–146. Springer, Heidelberg (2010)
Di Giacomo, E., Didimo, W., Eades, P., Liotta, G.: 2-Layer Right Angle Crossing Drawings. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2011. LNCS, vol. 7056, pp. 156–169. Springer, Heidelberg (2011)
Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theoretical Computer Science 412(39), 5156–5166 (2011)
Dujmović, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. In: Proc. CATS 2010, pp. 19–24. ACS (2010)
Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: Proc. of 9th Australian Computer Science Conference, pp. 327–334 (1986)
Eades, P., Kelly, D.: Heuristics for drawing 2-layered networks. Ars Combin. 21, 89–98 (1986)
Eades, P., Whitesides, S.H.: Drawing graphs in two layers. Theoretical Computer Science 131(2), 361–374 (1994)
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)
Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Graph Algorithms Appl. 1 (1997)
van Kreveld, M.: The Quality Ratio of RAC Drawings and Planar Drawings of Planar Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 371–376. Springer, Heidelberg (2011)
Mutzel, P.: An alternative method to crossing minimization on hierarchical graphs. SIAM J. on Optimization 11(4), 1065–1080 (2001)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. on Syst., Man and Cyber. 11(2), 109–125 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Giacomo, E., Didimo, W., Grilli, L., Liotta, G., Romeo, S.A. (2012). Heuristics for the Maximum 2-layer RAC Subgraph Problem. In: Rahman, M.S., Nakano, Si. (eds) WALCOM: Algorithms and Computation. WALCOM 2012. Lecture Notes in Computer Science, vol 7157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28076-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-28076-4_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28075-7
Online ISBN: 978-3-642-28076-4
eBook Packages: Computer ScienceComputer Science (R0)