{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:30Z","timestamp":1761620970234},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540739487"},{"type":"electronic","value":"9783540739517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_36","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T10:18:03Z","timestamp":1187605083000},"page":"410-421","source":"Crossref","is-referenced-by-count":2,"title":["Fixed-Parameter Tractability for Non-Crossing Spanning Trees"],"prefix":"10.1007","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[]},{"given":"Christian","family":"Knauer","sequence":"additional","affiliation":[]},{"given":"Andreas","family":"Spillner","sequence":"additional","affiliation":[]},{"given":"Takeshi","family":"Tokuyama","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","first-page":"269","volume":"34","author":"V.G. Deineko","year":"2006","unstructured":"Deineko, V.G., Klinz, B., Woeginger, G.J.: Exact algorithms for the Hamilton cycle problem in planar graphs. Inf. Process. Lett.\u00a034, 269\u2013274 (2006)","journal-title":"Inf. Process. Lett."},{"key":"36_CR2","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"36_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"J. Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: Distance from triviality. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 162\u2013173. Springer, Heidelberg (2004)"},{"issue":"3","key":"36_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.comgeo.2005.11.006","volume":"34","author":"M. Hoffmann","year":"2006","unstructured":"Hoffmann, M., Okamoto, Y.: The minimum weight triangulation problem with few inner points. Computational Geometry\u00a034(3), 149\u2013158 (2006)","journal-title":"Computational Geometry"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Comput. Syst. Sci.\u00a063, 512\u2013530 (2001)","journal-title":"Journal of Comput. Syst. Sci."},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BF01990536","volume":"33","author":"K. Jansen","year":"1993","unstructured":"Jansen, K., Woeginger, G.J.: The complexity of detecting crossingfree configurations in the plane. BIT\u00a033, 580\u2013595 (1993)","journal-title":"BIT"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Knauer, C., Schramm, \u00c9., Spillner, A., Wolff, A.: Spanning trees with few crossings in geometric and topological graphs. In: Proc. European Workshop on Computational Geometry, pp. 195\u2013198 (2005)","DOI":"10.1007\/11602613_61"},{"issue":"2","key":"36_CR8","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.comgeo.2006.06.001","volume":"37","author":"C. Knauer","year":"2007","unstructured":"Knauer, C., Schramm, \u00c9., Spillner, A., Wolff, A.: Configurations with few crossings in topological graphs. Computational Geometry\u00a037(2), 104\u2013114 (2007)","journal-title":"Computational Geometry"},{"key":"36_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11917496_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"C. Knauer","year":"2006","unstructured":"Knauer, C., Spillner, A.: A fixed-parameter algorithm for the minimum weight triangulation problem based on small graph separators. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 49\u201357. Springer, Heidelberg (2006)"},{"issue":"2","key":"36_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/0404022","volume":"4","author":"J. Kratochv\u00edl","year":"1991","unstructured":"Kratochv\u00edl, J., Lubiw, A., Ne\u0161et\u0159il, J.: Noncrossing subgraphs in topological layouts. SIAM J. Disc. Math.\u00a04(2), 223\u2013244 (1991)","journal-title":"SIAM J. Disc. Math."},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Computing\u00a011, 329\u2013343 (1982)","journal-title":"SIAM J. Computing"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0022-0000(86)90030-9","volume":"32","author":"G.L. Miller","year":"1986","unstructured":"Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci.\u00a032, 265\u2013279 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR13","unstructured":"Spillner, A.: A faster algorithm for the minimum weight triangulation problem with few inner points. In: ACID 2005. Proc. Workshop Algorithms and Complexity in Durham, pp. 135\u2013146. KCL Publications (2005)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T21:07:57Z","timestamp":1684012077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}