Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut

Jünger, Michael and Mutzel, Petra (1993) Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut. [Preprint]

[img] Other
89Kb

Abstract

In this paper we investigate the problem of identifying a planar subgraph of maximum weight of a given edge weighted graph. In the theoretical part of the paper, the polytope of all planar subgraphs of a graph G is defined and studied. All subgraphs of a graph G, which are subdivisions of K5 or K3,3, turn out to define facets of this polytope. We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision of K5 or K3,3. These structures give us inequalities which are used as cutting planes.

Item Type:Preprint
Additional Information: This article was published in 1993 in the proceedings "Proceedings of the 3rd IPCO Conference (Integer Programming and Combinatorial Optimization)" (edited by Giovanni Rinaldi, L. Wolsey), pages 479-492.
Classifications:P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
M Methods > M.700 Planarization-based
ID Code:26
Alternative Locations:http://e-archive.informatik.uni-koeln.de/128/

Repository Staff Only: item control page

References

Booth, K. S. and Lueker, G. S. (1976) Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms. J. of Computer and System Sciences 13 335-379

Cai, J. and Han, X. and Tarjan, R. E. (1992) An O(mlogn)-Time Algorithm for the Maximal Planar Subgraph Problem. To appear in SIAM J. Comput.

Cimikowski, R. J. (1992) An Empirical Analysis of Graph Planarization Heuristics. Unpublished manuscript, Computer Science Dept., Montana State Univ.

Eades, P. and Foulds, L. R. and Giffin, J. W. (1982) An efficient Heuristic for Identifying a Maximum Weight Planar Subgraph. Combinatorial Mathematics IX, Lecture Notes in Mathematics No. 952, Springer-Verlag, Berlin.

Foulds, L. R. and Robinson, R. W. (1976) A Strategy for Solving the Plant Layout Problem. Operational Research Quaterly 27 845-855.

Foulds, L. R. and Robinson, R. W. (1978) Graph Theoretic Heuristics for the Plant Layout Problem. Int. J. Production Research 16 27-37.

Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman & Co., San Francisco.

Goldschmidt, O. and Takvorian, A. (1992) An efficient graph planarization two-phase heuristic. Technical Report ORP91-01, Dept. of Mech. Engr., Univ. Texas-Austin.

Grötschel, M. and Jünger, M. and Reinelt, G. (1984) A cutting for plane algorithm for the linear ordering problem. Operations Research 32 1195-1220.

Hopcroft, J. and Tarjan, R. E. (1974) Efficient planarity testing. J. ACM 21 549-568.

Jayakumar, R. and Thulasiraman, K. and Swamy, M. N. S. (1989) O(n²) Algorithms for Graph Planarization. IEEE Trans. on Computer-aided Design, 8 257-267.

Jünger, M. and Reinelt, G. and Thienel, S. (1992) Provably good solutions for the traveling salesman problem. Rep. No. 92.114, Angewandte Mathematik und Informatik, Universität zu Köln.

Kant, G. (1992) An O(n²) maximal planarization algorithm based on PQ-trees. Technical Report, RUU-CS-92-03, Dept. of Computer Science, Utrecht University.

Leung, J. (1992) A new graph-theoretic heuristic for facility layout. Management Science 38 594-605.

Liu, P. C. and Geldmacher, R. C. (1997) On the deletion of nonplanar edges of a graph. Proc. 10th. S-E Conf. on Comb., Graph Theory, and Comp., Boca Raton, FL 727-738.

Mutzel, P. (1992) A fast linear time embedding algorithm based on the Hopcroft-Tarjan planarity test. Rep. No. 92.107, Angewandte Mathematik und Informatik, Universität zu Köln.

Padberg, M. W. and Rinaldi, G. (1991) A branch and cut algorithm for the resolution of large-scale symmetric travelling salesman problems. SIAM Review 33 60-100.

Tamassia, R. and Di Battista, G. and Batini, C. (1988) Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics 18 61-79.