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

Jünger, Michael and Mutzel, Petra (1994) The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems. [Preprint]

WarningThere is a more recent version of this item available.

[img] Other
48Kb

Abstract

In Michael Jünger and Petra Mutzel [Algorithmica, 16 (1996)] 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 IN. 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, see Michael Jünger and Petra Mutzel [Proc. IPCO3 (1993)], the k-connected subgraph polytope M. Stoer [LNCS 1531 (1992)] 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:Preprint
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
M Methods > M.600 Planar
ID Code:24
Alternative Locations:http://e-archive.informatik.uni-koeln.de/165/

Available Versions of this Item

Repository Staff Only: item control page

References

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

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

Eades, P. (1993) Personal communication.

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

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

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

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

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

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

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

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.

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.

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

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

Mutzel, P. (1994) 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.

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

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

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11 109-125.

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

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.