×

Heuristics for the maximum outerplanar subgraph problem. (English) Zbl 1122.90416

Summary: Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.
The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.

MSC:

90C35 Programming involving graphs or networks
68R10 Graph theory (including graph drawing) in computer science
90C59 Approximation methods and heuristics in mathematical programming

Software:

DIMACS; LEDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E. and J. Lenstra. (1997). Local Search in Combinatorial Optimization. John Wiley and Sons. · Zbl 0869.00019
[2] Aarts, E. and P. van Laarhoven. (1985). ”Statistical Cooling: A General Approach to Combinatorial Optimization Problems.” Philips J. Res. 40, 193–226.
[3] Aragon, C.R., D.S. Johnson, L.A. McGeoch, and C. Schevon. (1991). ”Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning.” Oper. Res. 3(39), 378–406. · Zbl 0739.90055
[4] Boyer, J. and W. Myrvold. (1999). ”Stop Minding Your P’s and Q’s: A Simplified O(n) Planar Embedding Algorithm.” In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. pp. 140–146. · Zbl 0938.68064
[5] Brehaut, W. (1977). ”An Efficient Outerplanarity Algorithm.” In Proceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. pp. 99–113. · Zbl 0405.05035
[6] Călinescu, G., C. Fernandes, U. Finkler, and H. Karloff. (1998). ”A Better Approximation Algorithm for Finding Planar Subgraphs.” J. Algorithms 27(2), 269–302. · Zbl 0919.68093 · doi:10.1006/jagm.1997.0920
[7] Călinescu, G., C. Fernandes, H. Karloff, and A. Zelikovsky. (2003). ”A New Approximation Algorithm for Finding Heavy Planar Subgraphs.” Algorithmica 36(2), 179–205. · Zbl 1045.68101 · doi:10.1007/s00453-002-1020-3
[8] Cimikowski, R. (1995a). ”An Analysis of Heuristics for the Maximum Planar Subgraph Problem.” In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms. pp. 322–331. · Zbl 0848.68072
[9] Cimikowski, R. (1997). ”An Analysis of Heuristics for Graph Planarization.” J. Inf. Opt. Sci. 18(1), 49–73. · Zbl 0878.68095
[10] Cimikowski, R. and D. Coppersmith. (1996). ”The Sizes of Maximal Planar, Outerplanar, and Bipartite Planar Subgraphs.” Discr. Math. 149, 303–309. · Zbl 0845.05032 · doi:10.1016/0012-365X(94)00326-E
[11] Felsner, S., G. Liotta, and S. Wismath. (2002). ”Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions.” In Proceedings of Graph Drawing: 9th International Symposium (GD’01), vol. 2265 of LNCS. pp. 328–342. · Zbl 1054.68584
[12] Galil, Z., G. Italiano, and N. Sarnak. (1999). ”Fully Dynamic Planarity Testing with Applications.” J. ACM 46(1), 28–91. · Zbl 1064.05502 · doi:10.1145/300515.300517
[13] Garey, M. and D. Johnson. (1979) Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman. · Zbl 0411.68039
[14] Glauber, R. (1963). ”Time-Dependent Statistics of the Ising Model.” Math. Phys. 4(2), 294–307. · Zbl 0145.24003 · doi:10.1063/1.1703954
[15] Goldschmidt, O. and A. Takvorian. (1994). ”An Efficient Graph Planarization Two-Phase Heuristic.” Networks 24, 69–73. · Zbl 0789.90083 · doi:10.1002/net.3230240203
[16] Guy, R. (1974). Combinatorics, London Math. Soc. Lecture Notes 13, Chapt. Outerthickness and outercoarseness of graphs, Cambridge University Press, pp. 57–60.
[17] Harary, F. (1971). Graph Theory. Addison-Wesley. · Zbl 0209.55404
[18] Hopcroft, J. and R. Tarjan. (1974). ”Efficient Planarity Testing.” J. ACM 21, 549–568. · Zbl 0307.68025 · doi:10.1145/321850.321852
[19] Johnson, D. (2002). ”A Theoretician’s Guide to the Experimental Analysis of Algorithms.” In Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. pp. 215–250.
[20] Johnson, D., C.R. Aragon, L.A. McGeoch, and C. Schevon. (1989). ”Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning.” Oper. Res. 6(37), 865–892. · Zbl 0698.90065 · doi:10.1287/opre.37.6.865
[21] Kant, G. (1992). ”An O(n2) Maximal Planarization Algorithm Based on PQ-Trees.” Technical Report, Utrecht University. Technical Report RUU-CS-92-03.
[22] Kant, G. (1996). ”Augmenting Auterplanar Graphs.” J. Algorithms 21, 1–25. · Zbl 0857.68081 · doi:10.1006/jagm.1996.0034
[23] Kirkpatrick, S., C. Gelatt, and M. Vecchi. (1983). ”Optimization by Simulated Annealing.” Science 220, 671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[24] LEDA. (2003). ”LEDA Version 4.3 (commercial).” Available at http://www.algorithmic-solutions.com.
[25] Liebers, A. (2001). ”Planarizing Graphs–A Survey and Annotated Bibliography.” J. Graph Alg. and Appl. 5(1), 1–74. · Zbl 0966.05022
[26] Liu, P. and R. Geldmacher. (1977). ”On the Deletion of Nonplanar Edges of a Graph.” In Proceedings of the 10th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. pp. 727–738. · Zbl 0429.05036
[27] Maheshwari, A. and N. Zeh. (1999). ”External Memory Algorithms for Outerplanar Graphs.” In Proceedings of the 10th International Symposium on Algorithms and Computations, Vol. 1741 of LNCS. pp. 307–316. · Zbl 0964.68111
[28] Manning, J. and M. Atallah. (1992). ”Fast Detection and Display of Symmetry in Outerplanar Graphs.” Discr. Appl. Math. 39(1), 13–35. · Zbl 0768.68165 · doi:10.1016/0166-218X(92)90112-N
[29] Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. (1953). ”Equation of State Calculation by Fast Computing Machines.” J. Chem. Phys. 21, 1087–1091. · doi:10.1063/1.1699114
[30] Mitchell, S. (1979). ”Linear Algorithms to Recognize Outerplanar and Maximal Outerplanar Graphs.” Inf. Proc. Lett. 9(5), 177–189. · Zbl 0444.68055
[31] Mutzel, P., T. Odenthal, and M. Scharbrodt. (1998). ”The Thickness of Graphs: A Survey.” Graphs Comb. 14, 59–73. · Zbl 0896.05020 · doi:10.1007/PL00007219
[32] Poranen, T. (2003). ”Apptopinv–User’s guide.” Technical Report A-2003-3, University of Tampere, Department of Computer Sciences.
[33] Poranen, T. (2004). ”A Simulated Annealing Algorithm for Determining Maximum Planar Subgraphs.” Int. J. Comput. Math. 81(5), 555 – 568. · Zbl 1055.05144 · doi:10.1080/00207160410001684352
[34] Reeves, C. (ed.). (1995). Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill. · Zbl 0942.90500
[35] Resende, M. and C. Ribeiro. (1997). ”A GRASP for Graph Planarization.” Networks 29, 173–189. · Zbl 0885.90112 · doi:10.1002/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E
[36] Shih, W.-K. and W.-L. Hsu. (1999). ”A New Planarity Test.” Theor. Comput. Sci. 223, 179–191. · Zbl 0930.05092 · doi:10.1016/S0304-3975(98)00120-0
[37] Syslo, M. (1978). ”Outerplanar Graphs: Characterizations, Testing, Coding and Counting.” Bull. Acad. Polon. Sci. Sèr. Sci. Math. Astronom. Phys. 26(8), 675–684. · Zbl 0396.05014
[38] Syslo, M. and M. Iri. (1979). ”Efficient Outerplanarity Testing.” Fund. Inf. II, 261–275. · Zbl 0443.68047
[39] van Laarhoven, P. and E. Aarts. (1987). Simulated Annealing: Theory and Applications. Kluwer. · Zbl 0643.65028
[40] Vrtò, I. (2002). ”Crossing Numbers of Graphs: A Bibliography.” Available at ftp://ifi.savba.sk/pub/imrich/crobib.ps.gz.
[41] Wiegers, M. (1984). ”Recognizing Outerplanar Graphs in Linear Time.” In Graph-Theoretic Concepts in Computer Science, International Workshop WG’86, Vol. 246 of LNCS. pp. 165–176.
[42] Yannakakis, M. (1978). ”Node- and Edge-Deletion NP-Complete Problems.” In Proceedings of the 10th Annual ACM Symposium on Theory of Computing. pp. 253–264. · Zbl 1282.68131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.