A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract)

Jünger, Michael and Lee, Eva K. and Mutzel, Petra and Odenthal, Thomas (1998) A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_46).

Full text not available from this repository.

Abstract

We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_46
Classifications:G Algorithms and Complexity > G.700 Layering
G Algorithms and Complexity > G.420 Crossings
ID Code:69

Repository Staff Only: item control page

References

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Algorithms for drawing graphs: An annotated bibliography. Computational Geometry: Theory and Applications 4 (1994) 235-282.

Eades, P., Kelly, D.: Heuristics for Reducing Crossings in 2-Layered Networks. Ars Combinatoria 21-A (1986) 89-98.

Eades, P., Wormland, N.C.: Edge Crossings in Drawings of Bipartite Graphs. Algorithmica 11 (1994) 379-403.

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

Fukuda, K.: Face Lattices. Personal Communication (1996)

Garey, M.R., Johnson, D.S.: Crossing Number is NP-Complete. SIAM Journal on Algebraic and Discrete Methods 4 (1983) 312-316.

Grötschel, M., Jünger, M., Reinelt, G.: Facets of the linear ordering polytope. Mathematical Programming 33 (1985) 43-60.

Harary, F.: Determinants, permanents and bipartite graphs. Mathematical Magazine 42 (1969) 146-148.

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

Himsolt, M.: Personal Communication (1997).

Jünger, M., Mutzel, P.: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. Journal of Graph Algorithms and Applications (JGAA), (http://www.cs.brown.edu/publications/jgaa/), No. 1, Vol. 1, (1997) 1-25.

Kusiak, A., Wang, J.: Dependency Analysis in Constraint Negotiation. IEEE Trans. Sys. Man, Cybern. 25 (1995) 1301-1313.

May, M., Szkatula, K.: On the bipartite crossing number. Control and Cybernetics 17 No. 1 (1988) 85-97.

Mutzel, P.: An Alternative Method for Crossing Minimization. Lecture Notes in Computer Science LNCS 1190 (1997) 318-333.

Richter, B.R., Thomassen, C.: A survey on crossing numbers. Manuscript, Carleton University and The Technical University of Denmark (1994).

Shahrokhi, F., Szelky, L.A., Vrt'o, I.: Crossing Number of Graphs, Lower Bound Techniques and Algorithms: A Survey. Lecture Notes in Computer Science LNCS 894 (1995) 131-142.

Schieh, F., McCreary, C.: Directed Graphs Drawing by Clan-Based Decomposition. Lecture Notes in Computer Science LNCS 1027 (1996) 472-482.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for Visual Understading of Hierarchical System Structures. IEEE Trans. Syst. Man, Cybern. SMC-11 (1981) 109-125.

Tomii, N., Kambayashi, Y., Shunzo, Y.: On Planarization Algorithms of 2-Level Graphs. Paper of tech. group on electronic computers, IECEJ, EC77-38 (1977) 1-12.

Valls, V., Marti, R., Lino, P,: A Branch and Bound Algorithm for Minimizing the Number of Crossing Arcs in Bipartite Graphs. Journal of Operational Research 90 (1996a) 303-319.

Valls, V., Marti, R., Lino, P,: A tabu thresholding algorithm for arc crossing minimization in bipartite graphs. Annals of Opertaions Research 63 (1996b) 223-251.

Warfield, J.N.: Crossing Theory and Hierachy Mapping. IEEE Trans. Syst. Man, Cybern. SCM-7 (1997) 505-523.

Watkins, M.E.: A special crossing number for bipartite graphs: a research problem. Annals of New York Academy of Sciences 175 (1970) 405-410.