The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems

Jünger, Michael and Mutzel, Petra (1995) The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 119-130 (Official URL:

This is the latest version of this item.

Full text not available from this repository.


In [JM94] we used a branch and cut algorithm in order to determine a maximum weight planar subgraph of a given graph. One of the motivations was to produce a nice drawing of a given graph by drawing the found maximum planar subgraph, and then augmenting this drawing by the removed edges. Our experiments indicate that drawing algorithms for planar graphs which require 2- or 3-connectivity, resp. degree-constraints, in addition to planarity often give "nicer" results. Thus we are led to the following problems: (1) Find a maximum planar subgraph with maximum degree d \in \mathbb{N}. (2) Augment a planar graph to a k-connected planar graph. (3) Find a maximum planar k-connected subgraph of a given k-connected graph. (4) Given a graph G, which is not necessarily planar and not necessarily k-connected, determine a new graph H by removing r edges and adding a edges such that the new graph H is planar, spanning, k-connected, each node v has degree at most D(v) and r + a is minimum. Problems (1), (2) and (3) have been discussed in the literature, we argue that a solution to the newly defined problem (4) is most useful for our goal. For all four problems we give a polyhedral formulation by defining different linear objective functions over the same polytope which is the intersection of the planar subgraph polytope [JM93], the k-connected subgraph polytope [S92] and the degree-constrained subgraph polytope. We point out why we are confident that a branch and cut algorithm for the new problem will be an implementable and useful tool in automatic graph drawing.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_363
Classifications:G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.420 Crossings
ID Code:119

Available Versions of this Item

Repository Staff Only: item control page


Beck, H.K.B., H.-P. Galil, R. Henkel, and E. Sedlmayr: Chemistry in circumstellar shells, I. Chromospheric radiation fields and dust formation in optically thin shells of M-giants. Astron. Astrophys. 265 (1992) 626-642.

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

Eades, P.: Personal communication (1993).

Eades, P. and J. Marks: Personal communication (1994).

Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discr. Math. 5 (1992) 25-53.

Himsolt, M.: Konzeption und Implementierung von Grapheneditoren. Disertation, Universität Passau (1993).

Hsu, T.-S. and V. Ramachandran: A linear time algorithm for triconnectivity augmentation. Proc. 32th Annual Symp. on Found. of Comp. Science, Puerto Rico (1991) 548-559.

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

Jünger, M. and P. Mutzel: Solving the Maximum Planar Subgraph Problem by Branch and Cut. Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization (IPCO 3), Erice (1993) 479-492.

Jünger, M. and P. Mutzel: Maximum planar subgraphs and nice embeddings: Practical layout tool. to appear in Algorithmica, special issue on Graph Drawing, Edit. by G. Di Battista and R. Tamassia (1994).

Jayakumur, R., K. Thulasiraman and M.N.S. Swamy: 0(n^2) Algorithms for Graph Planarization. IEEE Trans. on Computer-aided Design 8 (1989) 257-267.

Kant, G.: An O(n^2) Maximal Planarization Algorithm based on PQ-trees. Technical Report, RUU-CS-92-03, Dept. of Computer Science, Utrecht University (1992).

Kant, G.: Algorithms for Drawing Planar Graphs. Ph.D.-Thesis, Utrecht University (1993).

Mutzel, P.: The Maximum Planar Subgraph Problem. Dissertation, Universität Köln (1994).

Mutzel, P.:s-Chorded Cycle Graphs and their Relation to the Planar Subgraph Polytope. Technical Report No. 94-161, Angewandte Mathematik und Informatik, Universität zu Köln (1994)

Rosenthal, A. and A. Goldner: Smallest augmentation to biconnect a graph SIAM J. on Computing 6 (1977) 55-66.

Stoer, M.: Design of Survivable Networks. Lecture Notes in Mathematics, Springer-Verlag, Berlin (1992).

Sugiyama, K., S. Tagawa, and M. Toda: Methods for Visual Understanding of Hierarchical Systems. IEEE Trans. on Systems, Man and Cybernetics, SMC-11, 2 (1981) 109-125.

Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987) 421-444.

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