{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:12:55Z","timestamp":1743005575845,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":27,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_254","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:01:26Z","timestamp":1219662086000},"page":"1448-1453","source":"Crossref","is-referenced-by-count":0,"title":["Graph Planarization"],"prefix":"10.1007","author":[{"given":"Mauricio G.C.","family":"Resende","sequence":"first","affiliation":[]},{"given":"Celso C.","family":"Ribeiro","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"254_CR1_254","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"Angluin D, Valiant LG (1979) Probabilistic algorithms for Hamiltonian circuits and matchings. J\u00a0Comput Syst Sci 18:155\u2013190","journal-title":"J. Comput. Syst. Sci."},{"key":"254_CR2_254","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth K, Lueker G (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J\u00a0Comput Syst Sci 13:335\u2013379","journal-title":"J. Comput. Syst. Sci."},{"key":"254_CR3_254","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/0222068","volume":"22","author":"J. Cai","year":"1993","unstructured":"Cai J, Han X, Tarjan R (1993) An O(m log n)-time algorithm for the maximal planar subgraph problem. SIAM J Comput 22:1142\u20131162","journal-title":"SIAM J. Comput."},{"key":"254_CR4_254","unstructured":"Chiba T, Nishioka I, Shirakawa I (1979) An algorithm of maximal planarization of graphs. In: Proc. 1979 IEEE Symp. Circuits and Sys., pp 649\u2013652"},{"key":"254_CR5_254","unstructured":"Cimikowski RJ (1995) An analysis of heuristics for the maximum planar subgraph problem. In: Proc. 6th ACM-SIAM Symp. Discrete Algorithms, pp 322\u2013331"},{"key":"254_CR6_254","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"1","author":"G. Di Battista","year":"1994","unstructured":"Di Battista G, Eades P, Tamassia R, Tollis IG (1994) Algorithms for drawing graphs: An annotated bibliography. Comput Geom Th Appl 1:235\u2013282","journal-title":"Comput. Geom. Th. Appl."},{"key":"254_CR7_254","doi-asserted-by":"crossref","unstructured":"Di Battista G, Tamassia R (1989) Incremental planarity testing. Proc. 30th IEEE Symp. FOCS, pp 436\u2013441","DOI":"10.1109\/SFCS.1989.63515"},{"key":"254_CR8_254","series-title":"Lecture Notes Math.","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BFb0061982","volume-title":"\u00a0","author":"P. Eades","year":"1982","unstructured":"Eades P, Foulds LR, Giffin JW (1982) An efficient heuristic for identifying a\u00a0maximum weight planar subgraph. In: Lecture Notes Math, vol\u00a0952. Springer, Berlin, pp 239\u2013251"},{"key":"254_CR9_254","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01096763","volume":"6","author":"T.A. Feo","year":"1995","unstructured":"Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J\u00a0Global Optim 6:109\u2013133","journal-title":"J. Global Optim."},{"key":"254_CR10_254","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1057\/jors.1976.174","volume":"27","author":"L.R. Foulds","year":"1976","unstructured":"Foulds LR, Robinson RW (1976) A\u00a0strategy for solving the plant layout problem. Oper Res Quart 27:845\u2013855","journal-title":"Oper. Res. Quart."},{"key":"254_CR11_254","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1080\/00207547808929997","volume":"16","author":"L.R. Foulds","year":"1978","unstructured":"Foulds LR, Robinson RW (1978) Graph theoretic heuristics for the plant layout problem. Internat J Production Res 16:27\u201337","journal-title":"Internat. J. Production Res."},{"key":"254_CR12_254","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/net.3230240203","volume":"24","author":"O. Goldschmidt","year":"1994","unstructured":"Goldschmidt O, Takvorian A (1994) An efficient graph planarization two-phase heuristic. Networks 24:69\u201373","journal-title":"Networks"},{"key":"254_CR13_254","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1111\/j.1475-3995.1995.tb00007.x","volume":"2","author":"M. Hasan","year":"1995","unstructured":"Hasan M, Osman IH (1995) Local search algorithms for the maximal planar layout problem. Internat Trans Oper Res 2:89\u2013106","journal-title":"Internat. Trans. Oper. Res."},{"key":"254_CR14_254","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft J, Tarjan RE (1974) Efficient planarity testing. J\u00a0ACM 21:549\u2013568","journal-title":"J. ACM"},{"key":"254_CR15_254","doi-asserted-by":"crossref","unstructured":"J\u00fcnger M, Leipert S, Mutzel P (1998) A\u00a0note on computing a\u00a0maximal planar subgraph using PQ-trees. Techn Report Inst Informatik Univ K\u00f6ln 98.320","DOI":"10.1109\/43.709399"},{"key":"254_CR16_254","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02086607","volume":"16","author":"M. J\u00fcnger","year":"1996","unstructured":"J\u00fcnger M, Mutzel P (1996) Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica 16:33\u201359","journal-title":"Algorithmica"},{"key":"254_CR17_254","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/ijoc.11.1.44","volume":"11","author":"M. Laguna","year":"1999","unstructured":"Laguna M, Marti R (1999) GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44\u201352","journal-title":"INFORMS J. Comput."},{"key":"254_CR18_254","first-page":"215","volume-title":"An algorithm for planarity testing of graphs. Proc. Theory of Graphs Internat. Symp","author":"A Lempel","year":"1966","unstructured":"Lempel A, Even S, Cedarbaum I (1966) An algorithm for planarity testing of graphs. Proc. Theory of Graphs Internat. Symp. Gordon and Breach, New York, pp 215\u2013232"},{"key":"254_CR19_254","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Wiley, New York"},{"key":"254_CR20_254","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1287\/mnsc.38.4.594","volume":"38","author":"J. Leung","year":"1992","unstructured":"Leung J (1992) A\u00a0new graph-theoretic heuristic for facility layout. Managem Sci 38:594\u2013605","journal-title":"Managem. Sci."},{"key":"254_CR21_254","unstructured":"Liu PC, Geldmacher RC (1977) On the deletion of nonplanar edges of a\u00a0graph. In: Proc. 10th SE Conf. Comb., Graph Theory, and Comput., pp 727\u2013738"},{"key":"254_CR22_254","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E","volume":"29","author":"M.G.C. Resende","year":"1997","unstructured":"Resende MGC, Ribeiro CC (1997) A\u00a0GRASP for graph planarization. Networks 29:173\u2013189","journal-title":"Networks"},{"key":"254_CR23_254","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/326147.326153","volume":"25","author":"C.C. Ribeiro","year":"1999","unstructured":"Ribeiro CC, Resende MGC (1999) Algorithm 797: FORTAN subroutines for approximate solution of graph planarization problems using GRASP. ACM Trans Math Softw 25:341\u2013352","journal-title":"ACM Trans. Math. Software"},{"key":"254_CR24_254","series-title":"Lecture Notes Math.","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0088963","volume-title":"Design of survivable networks","author":"M. Stoer","year":"1992","unstructured":"Stoer M (1992) Design of survivable networks. Lecture Notes Math, vol\u00a01531. Springer, Berlin"},{"key":"254_CR25_254","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1126\/science.245.4923.1221","volume":"245","author":"Y. Takefuji","year":"1989","unstructured":"Takefuji Y, Lee KC (1989) A\u00a0near-optimum parallel planarization algorithm. Science 245:1221\u20131223","journal-title":"Science"},{"key":"254_CR26_254","doi-asserted-by":"publisher","first-page":"1582","DOI":"10.1109\/43.103509","volume":"10","author":"Y. Takefuji","year":"1991","unstructured":"Takefuji Y, Lee K-C, Cho YB (1991) Comments on an O(n2)algorithm for graph planarization. IEEE Trans Computer-Aided Design 10:1582\u20131583","journal-title":"IEEE Trans. Computer-Aided Design"},{"key":"254_CR27_254","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/21.87055","volume":"18","author":"R. Tamassia","year":"1988","unstructured":"Tamassia R, DiBattista G (1988) Automatic graph drawing and readability of diagrams. IEEE Trans Syst, Man Cybern 18:61\u201379","journal-title":"IEEE Trans. Syst., Man Cybern."}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T10:07:56Z","timestamp":1720692476000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_254","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}