{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:44:49Z","timestamp":1759063489932},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2005,1]]},"DOI":"10.1007\/s10732-005-6999-6","type":"journal-article","created":{"date-parts":[[2005,5,12]],"date-time":"2005-05-12T08:20:01Z","timestamp":1115886001000},"page":"59-88","source":"Crossref","is-referenced-by-count":3,"title":["Heuristics for the Maximum Outerplanar Subgraph Problem"],"prefix":"10.1007","volume":"11","author":[{"given":"Timo","family":"Poranen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6999_CR1","unstructured":"Aarts, E. and J. Lenstra. (1997). Local Search in Combinatorial Optimization. John Wiley and Sons."},{"key":"6999_CR2","first-page":"193","volume":"40","author":"E. Aarts","year":"1985","unstructured":"Aarts, E. and P. van Laarhoven. (1985). \u201cStatistical Cooling: A General Approach to Combinatorial Optimization Problems.\u201d Philips J. Res. 40, 193\u2013226.","journal-title":"Philips J. Res."},{"issue":"39","key":"6999_CR3","first-page":"378","volume":"3","author":"C.R. Aragon","year":"1991","unstructured":"Aragon, C.R., D.S. Johnson, L.A. McGeoch, and C. Schevon. (1991). \u201cOptimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning.\u201d Oper. Res. 3(39), 378\u2013406.","journal-title":"Oper. Res."},{"key":"6999_CR4","unstructured":"Boyer, J. and W. Myrvold. (1999). \u201cStop Minding Your P\u2019s and Q\u2019s: A Simplified O(n) Planar Embedding Algorithm.\u201d In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. pp. 140\u2013146."},{"key":"6999_CR5","unstructured":"Brehaut, W. (1977). \u201cAn Efficient Outerplanarity Algorithm.\u201d In Proceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. pp. 99\u2013113."},{"issue":"2","key":"6999_CR6","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1006\/jagm.1997.0920","volume":"27","author":"G. C\u0103linescu","year":"1998","unstructured":"C\u0103linescu, G., C. Fernandes, U. Finkler, and H. Karloff. (1998). \u201cA Better Approximation Algorithm for Finding Planar Subgraphs.\u201d J. Algorithms 27(2), 269\u2013302.","journal-title":"J. Algorithms"},{"issue":"2","key":"6999_CR7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s00453-002-1020-3","volume":"36","author":"G. C\u0103linescu","year":"2003","unstructured":"C\u0103linescu, G., C. Fernandes, H. Karloff, and A. Zelikovsky. (2003). \u201cA New Approximation Algorithm for Finding Heavy Planar Subgraphs.\u201d Algorithmica 36(2), 179\u2013205.","journal-title":"Algorithmica"},{"key":"6999_CR8","unstructured":"Cimikowski, R. (1995a). \u201cAn Analysis of Heuristics for the Maximum Planar Subgraph Problem.\u201d In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms. pp. 322\u2013331."},{"issue":"1","key":"6999_CR9","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1080\/02522667.1997.10699312","volume":"18","author":"R. Cimikowski","year":"1997","unstructured":"Cimikowski, R. (1997). \u201cAn Analysis of Heuristics for Graph Planarization.\u201d J. Inf. Opt. Sci. 18(1), 49\u201373.","journal-title":"J. Inf. Opt. Sci."},{"key":"6999_CR10","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0012-365X(94)00326-E","volume":"149","author":"R. Cimikowski","year":"1996","unstructured":"Cimikowski, R. and D. Coppersmith. (1996). \u201cThe Sizes of Maximal Planar, Outerplanar, and Bipartite Planar Subgraphs.\u201d Discr. Math. 149, 303\u2013309.","journal-title":"Discr. Math."},{"key":"6999_CR11","doi-asserted-by":"crossref","unstructured":"Felsner, S., G. Liotta, and S. Wismath. (2002). \u201cStraight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions.\u201d In Proceedings of Graph Drawing: 9th International Symposium (GD\u201901), vol. 2265 of LNCS. pp. 328\u2013342.","DOI":"10.1007\/3-540-45848-4_26"},{"issue":"1","key":"6999_CR12","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/300515.300517","volume":"46","author":"Z. Galil","year":"1999","unstructured":"Galil, Z., G. Italiano, and N. Sarnak. (1999). \u201cFully Dynamic Planarity Testing with Applications.\u201d J. ACM 46(1), 28\u201391.","journal-title":"J. ACM"},{"key":"6999_CR13","unstructured":"Garey, M. and D. Johnson. (1979) Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman."},{"issue":"2","key":"6999_CR14","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1063\/1.1703954","volume":"4","author":"R. Glauber","year":"1963","unstructured":"Glauber, R. (1963). \u201cTime-Dependent Statistics of the Ising Model.\u201d Math. Phys. 4(2), 294\u2013307.","journal-title":"Math. Phys."},{"key":"6999_CR15","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/net.3230240203","volume":"24","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt, O. and A. Takvorian. (1994). \u201cAn Efficient Graph Planarization Two-Phase Heuristic.\u201d Networks 24, 69\u201373.","journal-title":"Networks"},{"key":"6999_CR16","unstructured":"Guy, R. (1974). Combinatorics, London Math. Soc. Lecture Notes 13, Chapt. Outerthickness and outercoarseness of graphs, Cambridge University Press, pp. 57\u201360."},{"key":"6999_CR17","unstructured":"Harary, F. (1971). Graph Theory. Addison-Wesley."},{"key":"6999_CR18","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J. and R. Tarjan. (1974). \u201cEfficient Planarity Testing.\u201d J. ACM 21, 549\u2013568.","journal-title":"J. ACM"},{"key":"6999_CR19","doi-asserted-by":"crossref","unstructured":"Johnson, D. (2002). \u201cA Theoretician\u2019s Guide to the Experimental Analysis of Algorithms.\u201d In Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges. pp. 215\u2013250.","DOI":"10.1090\/dimacs\/059\/11"},{"issue":"37","key":"6999_CR20","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"6","author":"D. Johnson","year":"1989","unstructured":"Johnson, D., C.R. Aragon, L.A. McGeoch, and C. Schevon. (1989). \u201cOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning.\u201d Oper. Res. 6(37), 865\u2013892.","journal-title":"Oper. Res."},{"key":"6999_CR21","unstructured":"Kant, G. (1992). \u201cAn O(n2) Maximal Planarization Algorithm Based on PQ-Trees.\u201d Technical Report, Utrecht University. Technical Report RUU-CS-92-03."},{"key":"6999_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1996.0034","volume":"21","author":"G. Kant","year":"1996","unstructured":"Kant, G. (1996). \u201cAugmenting Auterplanar Graphs.\u201d J. Algorithms 21, 1\u201325.","journal-title":"J. Algorithms"},{"key":"6999_CR23","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., C. Gelatt, and M. Vecchi. (1983). \u201cOptimization by Simulated Annealing.\u201d Science 220, 671\u2013680.","journal-title":"Science"},{"key":"6999_CR24","unstructured":"LEDA. (2003). \u201cLEDA Version 4.3 (commercial).\u201d Available at http:\/\/www.algorithmic-solutions.com."},{"issue":"1","key":"6999_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00032","volume":"5","author":"A. Liebers","year":"2001","unstructured":"Liebers, A. (2001). \u201cPlanarizing Graphs\u2014A Survey and Annotated Bibliography.\u201d J. Graph Alg. and Appl. 5(1), 1\u201374.","journal-title":"J. Graph Alg. and Appl."},{"key":"6999_CR26","unstructured":"Liu, P. and R. Geldmacher. (1977). \u201cOn the Deletion of Nonplanar Edges of a Graph.\u201d In Proceedings of the 10th South-Eastern Conference on Combinatorics, Graph Theory, and Computing. pp. 727\u2013738."},{"key":"6999_CR27","doi-asserted-by":"crossref","unstructured":"Maheshwari, A. and N. Zeh. (1999). \u201cExternal Memory Algorithms for Outerplanar Graphs.\u201d In Proceedings of the 10th International Symposium on Algorithms and Computations, Vol. 1741 of LNCS. pp. 307\u2013316.","DOI":"10.1007\/3-540-46632-0_31"},{"issue":"1","key":"6999_CR28","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0166-218X(92)90112-N","volume":"39","author":"J. Manning","year":"1992","unstructured":"Manning, J. and M. Atallah. (1992). \u201cFast Detection and Display of Symmetry in Outerplanar Graphs.\u201d Discr. Appl. Math. 39(1), 13\u201335.","journal-title":"Discr. Appl. Math."},{"key":"6999_CR29","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller. (1953). \u201cEquation of State Calculation by Fast Computing Machines.\u201d J. Chem. Phys. 21, 1087\u20131091.","journal-title":"J. Chem. Phys."},{"key":"6999_CR30","doi-asserted-by":"crossref","unstructured":"Mitchell, S. (1979). \u201cLinear Algorithms to Recognize Outerplanar and Maximal Outerplanar Graphs.\u201d Inf. Proc. Lett. 9(5), 177\u2013189.","DOI":"10.1016\/0020-0190(79)90075-9"},{"key":"6999_CR31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/PL00007219","volume":"14","author":"P. Mutzel","year":"1998","unstructured":"Mutzel, P., T. Odenthal, and M. Scharbrodt. (1998). \u201cThe Thickness of Graphs: A Survey.\u201d Graphs Comb. 14, 59\u201373.","journal-title":"Graphs Comb."},{"key":"6999_CR32","unstructured":"Poranen, T. (2003). \u201cApptopinv\u2014User\u2019s guide.\u201d Technical Report A-2003-3, University of Tampere, Department of Computer Sciences."},{"issue":"5","key":"6999_CR33","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1080\/00207160410001684352","volume":"81","author":"T. Poranen","year":"2004","unstructured":"Poranen, T. (2004). \u201cA Simulated Annealing Algorithm for Determining Maximum Planar Subgraphs.\u201d Int. J. Comput. Math. 81(5), 555 \u2013 568.","journal-title":"Int. J. Comput. Math"},{"key":"6999_CR34","unstructured":"Reeves, C. (ed.). (1995). Modern Heuristic Techniques for Combinatorial Problems. McGraw-Hill."},{"key":"6999_CR35","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E","volume":"29","author":"M. Resende","year":"1997","unstructured":"Resende, M. and C. Ribeiro. (1997). \u201cA GRASP for Graph Planarization.\u201d Networks 29, 173\u2013189.","journal-title":"Networks"},{"key":"6999_CR36","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(98)00120-0","volume":"223","author":"W.-K. Shih","year":"1999","unstructured":"Shih, W.-K. and W.-L. Hsu. (1999). \u201cA New Planarity Test.\u201d Theor. Comput. Sci. 223, 179\u2013191.","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"6999_CR37","first-page":"675","volume":"26","author":"M. Syslo","year":"1978","unstructured":"Syslo, M. (1978). \u201cOuterplanar Graphs: Characterizations, Testing, Coding and Counting.\u201d Bull. Acad. Polon. Sci. S\u00e8r. Sci. Math. Astronom. Phys. 26(8), 675\u2013684.","journal-title":"Bull. Acad. Polon. Sci. S\u00e9r. Sci. Math. Astronom. Phys."},{"key":"6999_CR38","first-page":"261","volume":"II","author":"M. Syslo","year":"1979","unstructured":"Syslo, M. and M. Iri. (1979). \u201cEfficient Outerplanarity Testing.\u201d Fund. Inf. II, 261\u2013275.","journal-title":"Fund. Inf."},{"key":"6999_CR39","doi-asserted-by":"crossref","unstructured":"van Laarhoven, P. and E. Aarts. (1987). Simulated Annealing: Theory and Applications. Kluwer.","DOI":"10.1007\/978-94-015-7744-1"},{"key":"6999_CR40","unstructured":"Vrt\u00f2, I. (2002). \u201cCrossing Numbers of Graphs: A Bibliography.\u201d Available at ftp:\/\/ifi.savba.sk\/pub\/imrich\/crobib.ps.gz."},{"key":"6999_CR41","unstructured":"Wiegers, M. (1984). \u201cRecognizing Outerplanar Graphs in Linear Time.\u201d In Graph-Theoretic Concepts in Computer Science, International Workshop WG\u201986, Vol. 246 of LNCS. pp. 165\u2013176."},{"key":"6999_CR42","doi-asserted-by":"crossref","unstructured":"Yannakakis, M. (1978). \u201cNode- and Edge-Deletion NP-Complete Problems.\u201d In Proceedings of the 10th Annual ACM Symposium on Theory of Computing. pp. 253\u2013264.","DOI":"10.1145\/800133.804355"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-005-6999-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-005-6999-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-005-6999-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T18:54:27Z","timestamp":1559242467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-005-6999-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["6999"],"URL":"https:\/\/doi.org\/10.1007\/s10732-005-6999-6","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}