{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T11:03:07Z","timestamp":1770980587039,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540755197","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_33","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"359-370","source":"Crossref","is-referenced-by-count":11,"title":["Determining the Smallest k Such That G Is k-Outerplanar"],"prefix":"10.1007","author":[{"given":"Frank","family":"Kammer","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D. Bienstock","year":"1990","unstructured":"Bienstock, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica\u00a05, 93\u2013109 (1990)","journal-title":"Algorithmica"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T., Abe, S., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. System Sci.\u00a030, 54\u201376 (1985)","journal-title":"J. Comput. System Sci."},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"33_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"33_CR6","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Tamassia, R.: Incremental planarity testing. In: Proc. 30th IEEE Symp. on Foundations of Computer Science, pp. 436\u2013441 (1989)","DOI":"10.1109\/SFCS.1989.63515"},{"key":"33_CR7","first-page":"235","volume":"9","author":"T. Gallai","year":"1964","unstructured":"Gallai, T.: Elementare Relationen bez\u00fcglich der Glieder und trennenden Punkte von Graphen. Magyar Tud. Akad. Mat. Kutato Int. Kozl.\u00a09, 235\u2013236 (1964)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"33_CR8","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, Calif (1979)"},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","first-page":"373","volume-title":"Automata, Languages and Programming","author":"Q.P. Gu","year":"2005","unstructured":"Gu, Q.P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n 3) time. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 373\u2013384. Springer, Heidelberg (2005)"},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.5486\/PMD.1966.13.1-4.15","volume":"13","author":"F. Harary","year":"1966","unstructured":"Harary, F., Prins, G.: The block-cutpoint-tree of a graph. Publicationes Mathematicae Debrecen\u00a013, 103\u2013107 (1966)","journal-title":"Publicationes Mathematicae Debrecen"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/3-540-44541-2_8","volume-title":"Graph Drawing","author":"C. Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR tree. In: Marks, J. (ed.) GD 2000. LNCS, vol.\u00a01984, pp. 77\u201390. Springer, Heidelberg (2001)"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01940648","volume":"16","author":"K. Mehlhorn","year":"1996","unstructured":"Mehlhorn, K., Mutzel, P.: On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica\u00a016, 233\u2013242 (1996)","journal-title":"Algorithmica"},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Reed, B.: Finding approximate separators and computing tree-width quickly. In: Proc.\u00a024th Annual ACM Symp. on Theory of Computing (STOC 1992), pp. 221\u2013228 (1992)","DOI":"10.1145\/129712.129734"},{"key":"33_CR14","unstructured":"R\u00f6hrig, H.: Tree Decomposition: A Feasibility Study, Master\u2019s thesis, Max-Planck-Institut f\u00fcr Informatik in Saarbr\u00fccken (1998)"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I Excluding a forest. J.Comb.Theory Series B\u00a035, 39\u201361 (1983)","journal-title":"J.Comb.Theory Series B"},{"key":"33_CR16","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III Planar tree-width. J.Comb.Theory Series B\u00a036, 49\u201364 (1984)","journal-title":"J.Comb.Theory Series B"},{"issue":"2","key":"33_CR17","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P.D. Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica\u00a014(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"33_CR18","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear algorithms. SIAM J. Comp.\u00a01, 146\u2013160 (1972)","journal-title":"SIAM J. Comp."},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"339","DOI":"10.2307\/1989545","volume":"34","author":"H. Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Amer. Math. Soc.\u00a034, 339\u2013362 (1932)","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T04:13:15Z","timestamp":1684037595000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_33","relation":{},"subject":[]}}