{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:58Z","timestamp":1725488998993},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540433095"},{"type":"electronic","value":"9783540458487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45848-4_6","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T14:47:53Z","timestamp":1186843673000},"page":"75-83","source":"Crossref","is-referenced-by-count":2,"title":["An Algorithm for Finding Large Induced Planar Subgraphs"],"prefix":"10.1007","author":[{"given":"Keith","family":"Edwards","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Graham","family":"Farr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"6_CR1","unstructured":"S. B\u00fchler, Planarity of Graphs, M.Sc. dissertation, University of Dundee, 2000."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/0222068","volume":"22","author":"J. Cai","year":"1993","unstructured":"J. Cai and X. Han and R. E. Tarjan, An O(mlog n)-Time Algorithm for the Maximal Planar Subgraph Problem, SIAM J. Comput. 22 (1993) 1142\u20131162.","journal-title":"SIAM J. Comput."},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1006\/jagm.1997.0920","volume":"27","author":"G. C\u0103linescu","year":"1998","unstructured":"G. C\u0103linescu, C. G. Fernandes, U. Finkler and H. Karloff, A better approximation algorithm for finding planar subgraphs, in: Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (Atlanta, GA, 1996); also: J. Algorithms 27 (1998) 269\u2013302.","journal-title":"J. Algorithms"},{"key":"6_CR4","unstructured":"Robert Cimikowski, An analysis of some heuristics for the maximum planar subgraph problem, in: Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms (San Francisco, CA, 1995), pp 322\u2013331, ACM, New York, 1995."},{"key":"6_CR5","unstructured":"G. Di Battista, Peter Eades, Roberto Tamassia and I. Tollis, Graph Drawing:A lgorithms for the Visualization of Graphs, Prentice Hall, 1999."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"H. N. Djidjev and S. M. Venkatesan, Planarization of graphs embedded on surfaces, in: M. Nagl (ed.), Proc. 21st Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201995) (Aachen, 1995), Lecture Notes in Comput. Sci., 1017, Springer, Berlin, 1995, pp. 62\u201372.","DOI":"10.1007\/3-540-60618-1_66"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/0377-2217(85)90288-7","volume":"20","author":"M. E. Dyer","year":"1985","unstructured":"M. E. Dyer, L. R. Foulds and A. M. Frieze, Analysis of heuristics for finding a maximum weight planar subgraph, Eur. J. Operational Res. 20 (1985) 102\u2013114.","journal-title":"Eur. J. Operational Res."},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1006\/jctb.2000.2018","volume":"82","author":"K. Edwards","year":"2001","unstructured":"K. Edwards and G. Farr, Fragmentability of graphs, J. Combin. Theory (Ser. B) 82 (2001) 30\u201337.","journal-title":"J. Combin. Theory (Ser. B)"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"L. Faria, C. M. H. de Figueiredo and C. F. X. Mendon\u00e7a, Splitting number is NP-complete, in: Juraj Hromkovic and Ondrej S\u00fdkora (eds.), Proc. 24th Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG\u2019 98) (Smolenice Castle, Slovakia, 18-20 June 1998), Lecture Notes in Comput. Sci., 1517, Springer, 1998, pp. 285\u2013297.","DOI":"10.1007\/10692760_23"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/net.3230240203","volume":"24","author":"O. Goldschmidt","year":"1994","unstructured":"O. Goldschmidt and A. Takvorian, An efficient graph planarization two-phase heuristic, Networks 24 (1994) 69\u201373.","journal-title":"Networks"},{"issue":"1","key":"6_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00020","volume":"4","author":"M. M. Halld\u00f3rsson","year":"2000","unstructured":"Magn\u00fas M. Halld\u00f3rsson, Approximation of weighted independent set and hereditary subset problems, Journal of Graph Algorithms and Applications 4 (1) (2000) 1\u201316.","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"3","key":"6_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00003","volume":"1","author":"M. M. Halld\u00f3rsson","year":"1997","unstructured":"Magn\u00fas M. Halld\u00f3rsson and Hoong Chuin Lau, Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring, Journal of Graph Algorithms and Applications 1 (3) (1997) 1\u201313.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"J. P. Hutchinson, On genus-reducing and planarizing algorithms for embedded graphs, in: R. B. Richter (ed.), Graphs and Algorithms, Contemporary Mathematics 89, Amer. Math. Soc., Providence, RI, 1989.","DOI":"10.1090\/conm\/089\/1006473"},{"key":"6_CR14","first-page":"81","volume-title":"Perspect. Comput.","author":"J. P. Hutchinson","year":"1987","unstructured":"Joan P. Hutchinson and Gary L. Miller, On deleting vertices to make a graph of positive genus planar, Discrete algorithms and complexity (Kyoto, 1986), Perspect. Comput., 15, pp. 81\u201398, Academic Press, Boston, MA, 1987."},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"M. J\u00fcnger and P. Mutzel, The polyhedral approach to the maximum planar subgraph problem: new chances for related problems, Graph Drawing\u2019 94, pp. 119\u2013130.","DOI":"10.1007\/3-540-58950-3_363"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02086607","volume":"16","author":"M. J\u00fcnger","year":"1996","unstructured":"M. J\u00fcnger and P. Mutzel, Maximum planar subgraphs and nice embeddings: practical layout tools, Algorithmica 16 (1996) 33\u201359.","journal-title":"Algorithmica"},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1090\/S0002-9939-1974-0345861-4","volume":"45","author":"P. C. Kainen","year":"1974","unstructured":"P. C. Kainen, A generalization of the 5-color theorem, Proc. Amer. Math. Soc. 45 (1974) 450\u2013453.","journal-title":"Proc. Amer. Math. Soc."},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1137\/0208049","volume":"8","author":"M. S. Krishnamoorthy","year":"1979","unstructured":"M. S. Krishnamoorthy and N. Deo, Node-deletion NP-complete problems, SIAM J. Comput. 8 (1979) 619\u2013625.","journal-title":"SIAM J. Comput."},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J. M. Lewis","year":"1980","unstructured":"J. M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219\u2013230.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"6_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00032","volume":"5","author":"A. Liebers","year":"2001","unstructured":"Annegret Liebers, Planarizing graphs \u2014 a survey and annotated bibliography, Journal of Graph Algorithms and Applications 5 (1) (2001) 1\u201374.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"6_CR21","unstructured":"P. C. Liu and R. C. Geldmacher, On the deletion of nonplanar edges of a graph, Proc. 10th. S-E Conf. on Comb., Graph Theory, and Comp. 1977, Congressus Numerantium, No. 24 (1979) 727\u2013738."},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, The approximation of maximum subgraph problems, in: Proc. 20th Int. Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 700, Springer-Verlag, 1993, pp. 40\u201351.","DOI":"10.1007\/3-540-56939-1_60"},{"key":"6_CR23","unstructured":"P. Mutzel, The Maximum Planar Subgraph Problem, Ph.D. Thesis, Univ. zu K\u00f6ln, 1994."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45848-4_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T19:19:47Z","timestamp":1684005587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45848-4_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540433095","9783540458487"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45848-4_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}