Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools

Jünger, Michael and Mutzel, Petra (1993) Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools. [Preprint]

[img] Other
141Kb

Abstract

In automatic graph drawing a given graph has to be layed-out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard. We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good and in many cases provably optimum solutions for sparse graphs and very dense graphs. 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. For cliques contained in G, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover we introduce the subdivision inequalities, V2k inequalities and flower inequalities all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated. 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. Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature.

Item Type:Preprint
Additional Information: This article was published in 1996 by Springer in the journal "Algorithmica", volume 16, pages 33-59. DOI: 10.1007/BF02086607
Classifications:P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
M Methods > M.700 Planarization-based
ID Code:25
Alternative Locations:http://e-archive.informatik.uni-koeln.de/145/

Repository Staff Only: item control page

References

Booth, K. and Lueker G. (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences, 13 (1) 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. (1978) Graph Theoretic Heuristics for the Plant Layout Problem. Int. J. Production Research 16 27-37.

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. Graph Theory Applications. Universitext, Springer-Verlag, New York.

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.

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

Himsolt, M. (1993) Personal communication.

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.

Martin, A. (1993) Personal communication.

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.

Pulleyblank, W. R. (1989) Polyhedral combinatorics. In: G. L. Nemhauser, A.H.G. Rinnoy Kan and M.J. Todd (eds.) Handbook on Operations Research and Management Sciences: Networks, North Holland.

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.