Abstract
We study the problem of optimizing over the set of all combinatorial embeddings of a given planar graph. At IPCO’ 99 we presented a first characterization of the set of all possible embeddings of a given biconnected planar graph G by a system of linear inequalities. This system of linear inequalities can be constructed recursively using SPQR-trees and a new splitting operation. In general, this approach may not be practical in the presence of high degree vertices.
In this paper, we present an improvement of the characterization which allows us to deal efficiently with high degree vertices using a separation procedure. The new characterization exposes the connection with the asymmetric traveling salesman problem thus giving an easy proof that it is NP-hard to optimize arbitrary objective functions over the set of combinatorial embeddings.
Computational experiments on a set of over 11000 benchmark graphs show that we are able to solve the problem for graphs with 100 vertices in less than one second and that the necessary data structures for the optimization can be build in less than 12 seconds.
Partially supported by DFG-Grant Mu 1129/3-1, Forschungsschwerpunkt “E.ziente Algorithmen für diskrete Probleme und ihre Anwendungen”
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303–326, 1997.
G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956–997, 1996.
P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. Lecture Notes in Computer Science, 1272:331–344, 1998.
D. Bienstock and C. L. Monma. Optimal enclosing regions in planar graphs. Networks, 19(1):79–94, 1989.
D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93–109, 1990.
J. Cai. Counting embeddings of planar graphs using DFS trees. SIAM Journal on Discrete Mathematics, 6(3):335–352, 1993.
G. Carpaneto, M. Dell’Amico, and P. Toth. Exact solution of large scale asymmetric travelling salesman problems. ACM Transactions on Mathematical Software, 21(4):394–409, 1995.
S. Fialko and P. Mutzel. A new approximation algorithm for the planar augmentation problem. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 260–269, San Francisco, California, 1998.
A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. Lecture Notes in Computer Science, 894:286–297, 1995.
M. Jünger, S. Leipert, and P. Mutzel. A note on computing a maximal planar subgraph using PQ-trees. IEEE Transactions on Computer-Aided Design, 17(7):609–612, 1998.
P. Mutzel and R. Weiskircher. Optimizing over all combinatorial embeddings of a planar graph. Technical report, Max-Planck-Institut für Informatik, Saarbrücken, 1998.
P. Mutzel and R. Weiskircher. Optimizing over all combinatorial embeddings of a planar graph. In G. Cornuéjols, R. Burkard, and G. Wöginger, Eds, Proceedings of the Seventh Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1610 of LNCS, pages 361–376. Springer Verlag, 1999.
R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421–444, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mutzel, P., Weiskircher, R. (2000). Computing Optimal Embeddings for Planar Graphs. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_10
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive