Abstract
In automatic graph drawing a given graph has to be laid 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 graphG is defined and studied. All subgraphs of a graphG, which are subdivisions ofK 5 orK 3,3, turn out to define facets of this polytope. For cliques contained inG, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover, we introduce the subdivision inequalities,V 2k inequalities, and the 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 ofK 5 orK 3,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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Booth, K. S., and G. S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms,Journal of Computer and System Sciences 13 (1976), 335–379.
Cai, J., X. Han, and R. E. Tarjan, An O(m logn)-time algorithm for the maximal planar subgraph problem,SIAM Journal on Computing 22 (1993), 1142–1162.
Cimikowski, R. J., An empirical analysis of graph planarization heuristics, unpublished manuscript, Computer Science Dept, Montana State University (1992).
Eades P., L. R. Foulds, and J. W. Giffin. An efficient heuristic for identifying a maximum weight planar subgraph,Combinatorial Mathematics IX, Lecture Notes in Mathematics, Vol. 952, Springer-Verlag, Berlin (1982), pp. 239–251.
Foulds, L. R., Graph theory applications,Universitext, Springer-Verlag, New York (1992).
Foulds, L. R., and R. W. Robinson, A strategy for solving the plant layout problem,Operational Research Quaterly 27 (1976), 845–855.
Foulds, L. R., and R. W. Robinson, Graph theoretic heuristics for the plant layout problem,International Journal of Production Research 16 (1978), 27–37.
Garey, M. R., and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco (1979).
Goldschmidt, O., and A. Takvorian, An Efficient Graph Planarization Two-Phase Heuristic, Technical Report ORP91-01, Dept. of Mech. Engr., University of Texas, Austin (1992).
Grötschel, M., M. Jünger, and G. Reinelt, A cutting plane algorithm for the linear ordering problem,Operations Research 32 (1984), 1195–1220.
Himsolt, M., Konzeption und Implementierung von Grapheneditoren, Dissertation, Universität Passau (1993).
Himsolt, M., Personal communication (1993).
Hopcroft, J., and R. E. Tarjan, Efficient planarity testing,Journal of the Association for Computing Machinery 21 (1974), 549–568.
Jayakumar, R., K. Thulasiraman, and M. N. S. Swamy, O(n 2) algorithms for graph planarization,IEEE Transactions on Computer-aided Design 8 (1989), 257–267.
Jünger, M., G. Reinelt, and S. Thienel, Provably Good Solutions for the Traveling Salesman Problem, Rep. No. 92.114, Angewandte Mathematik und Informatik, Universität zu Köln (1992).
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).
Leung, J., A new graph-theoretic heuristic for facility layout,Management Science 38 (1992), 594–605.
Liu, P. C., and R. C. Geldmacher, On the deletion of nonplanar edges of a graph,Proc. 10th. S.-E. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, FL (1977), pp. 727–738.
Martin, A., Personal communication (1993).
Mutzel, P., A Fast Linear Time Embedding Algorithm Based on the Hopcroft-Tarjan Planarity Test, Report No. 92.107, Angewandte Mathematik und Informatik, Universität zu Köln (1992).
Padberg, M. W., and G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems,SIAM Review 33 (1991), 60–100.
Pulleyblank, W. R., 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, Amsterdam (1989).
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.
Author information
Authors and Affiliations
Additional information
Communicated by G. Di Battista and R. Tamassia.
Rights and permissions
About this article
Cite this article
Jünger, M., Mutzel, P. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16, 33–59 (1996). https://doi.org/10.1007/BF02086607
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02086607