{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:59Z","timestamp":1771036319977,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540775362","type":"print"},{"value":"9783540775379","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77537-9_17","type":"book-chapter","created":{"date-parts":[[2008,1,30]],"date-time":"2008-01-30T14:50:55Z","timestamp":1201704655000},"page":"159-170","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Extraction of Multiple Kuratowski Subdivisions"],"prefix":"10.1007","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[]},{"given":"Jens M.","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","unstructured":"OGDF - Open Graph Drawing Framework. University of Dortmund, Chair of Algorithm Engineering, Website under Construction (2007)"},{"issue":"5-6","key":"17_CR2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G. Battista Di","year":"1997","unstructured":"Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., Vargiu, F.: An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl.\u00a07(5-6), 303\u2013325 (1997)","journal-title":"Comput. Geom. Theory Appl."},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-540-24595-7_3","volume-title":"Graph Drawing","author":"J.M. Boyer","year":"2004","unstructured":"Boyer, J.M., Cortese, P.F., Patrignani, M., Di Battista, G.: Stop minding your P\u2019s and Q\u2019s: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 25\u201336. Springer, Heidelberg (2004)"},{"key":"17_CR4","first-page":"140","volume-title":"Proc. SODA 1999","author":"J.M. Boyer","year":"1999","unstructured":"Boyer, J.M., Myrvold, W.J.: Stop minding your P\u2019s and Q\u2019s: A simplified O(n) planar embedding algorithm. In: Proc. SODA 1999, pp. 140\u2013146. SIAM, Philadelphia, PA (1999)"},{"issue":"3","key":"17_CR5","doi-asserted-by":"crossref","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"J.M. Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: Simplified O(n) planarity by edge addition. Journal of Graph Algorithms an Applications\u00a08(3), 241\u2013273 (2004)","journal-title":"Journal of Graph Algorithms an Applications"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/11618058_4","volume-title":"Graph Drawing","author":"C. Buchheim","year":"2006","unstructured":"Buchheim, C., Chimani, M., Ebner, D., Gutwenger, C., J\u00fcnger, M., Klau, G.W., Mutzel, P., Weiskircher, R.: A branch-and-cut approach to the crossing number problem. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol.\u00a03843, pp. 37\u201348. Springer, Heidelberg (2006)"},{"key":"17_CR7","unstructured":"Chimani, M., Mutzel, P., Schmidt, J.M.: Efficient extraction of multiple Kuratowski subdivisions (TR). Technical Report TR07-1-002, Chair for Algorithm Engineering, Dep. of CS, University Dortmund (2007), \n                    \n                      http:\/\/ls11-www.cs.uni-dortmund.de\/people\/chimani\/"},{"issue":"1","key":"17_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J.R., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms\u00a013(1), 33\u201354 (1992)","journal-title":"J. Algorithms"},{"issue":"4","key":"17_CR9","doi-asserted-by":"crossref","first-page":"411","DOI":"10.7155\/jgaa.00077","volume":"7","author":"H. Fraysseix de","year":"2003","unstructured":"de Fraysseix, H., de Mendez, P.O.: On cotree-critical and DFS cotree-critical graphs. Journal of Graph Algorithms an Applications\u00a07(4), 411\u2013427 (2003)","journal-title":"Journal of Graph Algorithms an Applications"},{"issue":"2","key":"17_CR10","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02579375","volume":"5","author":"H. Fraysseix de","year":"1985","unstructured":"de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by Tr\u00e9maux orders. Combinatorica\u00a05(2), 127\u2013135 (1985)","journal-title":"Combinatorica"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"issue":"1","key":"17_CR12","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.: Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica\u00a016(1), 33\u201359 (1996)","journal-title":"Algorithmica"},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"K. Kuratowski","year":"1930","unstructured":"Kuratowski, K.: Sur le probl\u00e8me des corbes gauches en topologie. Fundamenta Mathematic\u00e6\u00a015, 271\u2013283 (1930)","journal-title":"Fundamenta Mathematic\u00e6"},{"key":"17_CR14","unstructured":"Schmidt, J.M.: Effiziente Extraktion von Kuratowski-Teilgraphen. Diploma thesis, Department of Computer Science, University of Dortmund (March 2007)"},{"issue":"4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"S.G. Williamson","year":"1984","unstructured":"Williamson, S.G.: Depth-first search and Kuratowski subgraphs. J. ACM\u00a031(4), 681\u2013693 (1984)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77537-9_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:15:48Z","timestamp":1619522148000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77537-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540775362","9783540775379"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77537-9_17","relation":{},"subject":[]}}