An Alternative Method to Crossing Minimization on Hierarchical Graphs (extended abstract)

Mutzel, Petra (1997) An Alternative Method to Crossing Minimization on Hierarchical Graphs (extended abstract). In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 318-333 (Official URL:

Full text not available from this repository.


A common method for drawing directed graphs is, as a first step, to partition the vertices into a set of k levels and then, as a second step, to permute the vertices within the levels such that number of crossings is minimized. We suggest an alternative method for second step, namely, removing the minimal number of edges such that the resulting graph is k-level planar. For the final diagram the removed edges are reinserted into a k-level planar drawing. Hence, instead of considering the k-level crossing minimization problem, we suggest solving the k-level planarization problem. In this paper we adress the case k=2. First, we give a motivation for our approach. Then, we adress the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is np-hard. Based on characterization of 2-level planar graphs, we give an integer linear programming formulation for the 2-level planarization problem. Moreover, we define and investigate the polytope 2LPS(G) associated with the set of all 2-level planar subgraphs of a given 2-level graph G. We will see that this polytope has full dimensionand and that the inqualities occuring in the integer linear description are facet-defining for 2LPS(G). The inqualities in the integer linear programming formulation can be separated in polynomial time, hence they can be used efficiently in a cutting plane method for solving practical instances of the 2-level planarization problem. Furthermore, we derive new inqualities that substantially improve the quality of the obtained solution. We report on first computational results.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_57
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:197

Repository Staff Only: item control page


G. Di Battista and E. Nardelli. Hirarchies and Planarity Theory. IEEE Transactions on Systems, Man and Cybernetics 18 (1988) 1035-1046.

Carpano, M.J. Automatic display of hierarchized graphs for computer aided decision analysis. IEEE Transactions on Systems, Man and Cybernetics, SMC-10, no. 11 (1980) 705-715.

Edmonds, J. Submodular functions, matroids and certain polyhedra. In Combinatorial Structures and Their Applications, Gordon and Breach, London (1970) 69-87.

Dresbach, S. A new heuristic layout algorithm for DAGs. In Derigs, Bachem & Drexl (eds.), Operations Research Proceedings 1994, Springer Verlag, Berlin (1994) 121-126.

Eades, P., and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria 21-A (1986) 327-334.

Eades, P., B.D. MacKay, and N.C. Wormald. On an edge crossing problem. Proc. 9th Australian Computer Science Conference, Australian National University (1986) 327-334.

Eades, P. and N.C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica 10 (1994)379-403.

Eades, P. and S. Whitesides. Drawing graphs in two layers. Theoretical computer science 131 (1994) 361-374.

Fukuda, A. Face Lattice. Personal Communication (1996).

Grötschel, M., L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(1981) 169-197.

Grötschel, M. and M.W. Padberg. Polyhedral theory. In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan, and D.B. Shmoys (eds.), The trevaling salesman problem: A guided tour of combinatorial optimization, Wiley-Interscience (1985).

Heath, L.S. and S.V. Pemmaraju: Recognizing leveled-planar DAGs in linear time. LNCS 1027, in: F. Brandenburg (ed.), Proc. on Graph Drawing '95, Passau (1996) 300-311.

Jünger, M. and Mutzel P. Solving the maximum planar subgraph problem by branch and cut. In: L.A. Wolsey and G. Rinaldi (eds.), Proc. of the 3rd IPCO Conference, Erice (1993) 479-492.

Jünger, M. and Mutzel P. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algoritmica 16, No. 1, Special Issue on Graph Drawing, G. Di Battista and R. Tamassia (eds.), (1996) 33-59, also Report No. 93.145, Universität zu Köln, (1993).

Jünger, M. and Mutzel P. Exact and heuristic algorithms for 2-layer straightline crossing minimization. LNCS 1027, in: F. Brandenburg (ed.), Proc. on Graph Drawing '95, Passau (1996) 337-348.

Jünger, M., G. Reinelt, and S. Thienel. Practical problem solving with cutting plane algorithms in combinatorial optimization. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20 (1995) 111-152.

Karp, R.M. and C.H. Papadimitriou. On linear characterizations of combinatorial optimization problems. Proc. of the 21st Annual Symp. on the Foundations of Computer Science IEEE (1980) 1-9.

Thomas Lengauer. Combinatorial Algorithms for Integrated Circuit Layout. John Wiley and Sons, 1990.

E. Mäkinen. Experiments on Drawing 2-level hierarchical graphs. Inern. J. Computer Math. 37 (1990) 129-135.

Mutzel, P. The maximum planar subgraph problem. Dissertation, Universität zu Köln (1994).

Padberg, M. and M.R. Rao. The russian method for linear inequalities III: Bounded Integer Programming. . GBA Working Paper 81-39, New-York University (1981).

Padberg, M. and L. Wolsey. Trees and Cuts. Annals of Discrete Mathematics 17(1983) 511-517.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.

Tomii, N., Y. Kambayashi, and Y. Shuzo. On planarization algorithms of 2-level graphs. Papers of tech. group on electronic computers, IECEJ, EC77-38 (1977) 1-12.

Ullman, J.D: Computational aspects of VLSI. Computer Science Press, Rockville, MD (1984).

Vingron, M., H.-P. Lenhof, and P. Mutzel. Computational molecular biology. ÄIn: Annotated bibliographies in combonatorial optimization, M. Dell'Amico, F. Maffioli, S. Martello (eds.), Chapter 23, to appear (1996).

Valls, V, R. Marti, and P. Lino. A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs. Journal of Operational Research 90 (1996) 303-319.

Warfield, J.N. Crossing theory and hierarchy mapping. IEEE Trans Syst. Man. Cybern., SMC-7 (1977) 505-523.

Waterman, M.S: and J.R. Griggs. Interval graphs and maps of DNA. Bull. Math. Biology 48, no. 2 (1986) 189-194.