Advances in the Planarization Method: Effective Multiple Edge Insertions

Chimani, Markus and Gutwenger, Carsten (2012) Advances in the Planarization Method: Effective Multiple Edge Insertions. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 87-98 (Official URL: 10.1007/978-3-642-25878-7_10).

Full text not available from this repository.


The planarization method is the strongest known method to heuristically find good solutions to the general crossing number problem in graphs: starting from a planar subgraph, one iteratively inserts edges,representing crossings via dummy nodes. In the recent years, several improvements both from the practical and the theoretical point of view have been made. We review these advances and conduct an extensive study of the algorithms’ practical implications. Thereby, we present the first implementation of an approximation algorithm for the crossing number problem of general graphs, and compare the obtained results with known exact crossing number solutions.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_10
Classifications:G Algorithms and Complexity > G.840 Planarization
ID Code:1244

Repository Staff Only: item control page


Batini, C., Talamo, M., Tamassia, R.: Computer aided layout of entity relationship diagrams. J. Syst. Software 4, 163–173 (1984)

Cabello, S., Mohar, B.: Crossing and Weighted Crossing Number of Near Planar Graphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 38–49. Springer, Heidelberg (2009)

Chimani, M.: Computing Crossing Numbers. PhD thesis, TU Dortmund, Germany (2008)

Chimani, M., Gutwenger, C., Mutzel, P., Wolf, C.: Inserting a vertex into a planar graph. In: Mathiru, C. (ed.) Proc. SODA 2009, pp. 375–383 (2009)

Chimani, M., Hliněný, P.: A tighter Insertion-Based Approximation of the Crossing Number. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 122–134. Springer, Heidelberg (2011)

Chimani, M., Hliněný, P., Mutzel, P.: Vertex insertion approximates the crossing number for apex. Europ. J. Comb. (to appear, 2011)

Chimani, M., Mutzel, P., Bomze, I.: A New Approach to Exact Crossing Minimization. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 284–296. Springer, Heidelberg (2008)

Chuzhoy, J., Makarychev, Y., Sidiropoulos, A.: On graph crossing number and edge planarization. In: Proc. SODA 2011, pp. 1050–1069. ACM Press (2011)

Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Computational Geometry 7(5-6), 303–326 (1997)

Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM Journal on Computing 25, 956–997 (1996)

Gutwenger, C.: Application of SPQR-Trees in the Planarization Approach for Drawing Graphs. PhD thesis, TU Dortmund, Germany (2010)

Gutwenger, C., Mutzel, P.: A Linear Time Implementation of SPQR Trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Gutwenger, C., Mutzel, P.: An Experimental Study of Crossing Minimization Heuristics. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 13–24. Springer,Heidelberg (2004)

Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41(4), 289–308 (2005)

Hliněný, P., Salazar, G.: On the Crossing Number of Almost Planar Graphs. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 162–173. Springer, Heidelberg (2007)

Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM Journal on Computing 2(3), 135–158 (1973)

Jünger, M., Leipert, S., Mutzel, P.: A note on computing a maximal planar subgraph using PQ-trees. IEEE Trans. Comp.-Aided Design 17(7), 609–612 (1998)

Ziegler, T.: Crossing Minimization in Automatic Graph Drawing. PhD thesis,Saarland University, Germany (2001)