{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:45:27Z","timestamp":1787503527289,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_22","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"277-288","source":"Crossref","is-referenced-by-count":5,"title":["Theory and Application of Width Bounded Geometric Separator"],"prefix":"10.1007","author":[{"given":"Bin","family":"Fu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Agarwal, P., Overmars, M., Sharir, M.: Computing maximally separated sets in the plane and independent sets in the intersection graph of unit graph. In: Proceedings of 15th ACM-SIAM symposium on discrete mathematics algorithms, pp. 509\u2013518. ACM-SIAM (2004)"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"P. Agarwal","year":"2002","unstructured":"Agarwal, P., Procopiuc, C.M.: Exact and approximation algorithms for clustering. Algorithmica\u00a033, 201\u2013226 (2002)","journal-title":"Algorithmica"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Graph separators: a parameterized view. In: Proceedings of 7th Internal computing and combinatorics conference, pp. 318\u2013327 (2001)","DOI":"10.1007\/3-540-44679-6_35"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Parameterized complexity: exponential speed-up for planar graph problems. In: Proceedings of 28st international colloquium on automata, languages and programming, pp. 261\u2013272 (2001)","DOI":"10.1007\/3-540-48224-5_22"},{"issue":"2","key":"22_CR5","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solution for parameterized independent set problem on disk graphs. Journal of Algorithms\u00a052(2), 134\u2013151 (2004)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"22_CR6","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1137\/S0895480191198768","volume":"7","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P., Thomas, R.: Planar Separator. SIAM J. Discr. Math.\u00a07(2), 184\u2013193 (1990)","journal-title":"SIAM J. Discr. Math."},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete mathematics\u00a086, 165\u2013177 (1990)","journal-title":"Discrete mathematics"},{"issue":"2","key":"22_CR8","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/0603022","volume":"3","author":"H.N. Djidjev","year":"1982","unstructured":"Djidjev, H.N.: On the problem of partitioning planar graphs. SIAM journal on discrete mathematics\u00a03(2), 229\u2013240 (1982)","journal-title":"SIAM journal on discrete mathematics"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H.N. Djidjev","year":"1997","unstructured":"Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta informatica\u00a034, 231\u2013234 (1997)","journal-title":"Acta informatica"},{"issue":"12","key":"22_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"3","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Information processing letters\u00a03(12), 133\u2013137 (1981)","journal-title":"Information processing letters"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Fu, B., Wang, W.: A $2^{O(n^{1-1\/d}\\log n)}$ -time algorithm for d-dimensional protein folding in the HP-model. In: Proceedings of 31st international colloquium on automata, languages and programming, pp. 630\u2013644 (2004)","DOI":"10.1007\/978-3-540-27836-8_54"},{"key":"22_CR12","unstructured":"Fu, B., Chen, Z.: Sublinear-time algorithms for width-bounded geometric separator and their application to protein side-chain packing problem (submitted)"},{"key":"22_CR13","unstructured":"Gazit, H.: An improved algorithm for separating a planar graph, manuscript, USC (1986)"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separation theorem for graphs of bounded genus. Journal of algorithm\u00a0(5), 391\u2013407 (1984)","journal-title":"Journal of algorithm"},{"key":"22_CR15","volume-title":"Handbook of combinatorics","author":"R. Graham","year":"1996","unstructured":"Graham, R., Gr\u00f6tschel, M., Lov\u00e1sz, L.: Handbook of combinatorics, vol.\u00a0I. MIT Press, Cambridge (1996)"},{"key":"22_CR16","unstructured":"Hales, T.C.: A computer verification of the Kepler conjecture. In: Proceedings of the ICM, Beijing, vol.\u00a03, pp. 795\u2013804 (2002)"},{"issue":"2","key":"22_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formula and their uses. SIAM journal on computing\u00a011(2), 329\u2013343 (1982)","journal-title":"SIAM journal on computing"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.: A separator theorem for planar graph. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"3","key":"22_CR19","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.: Applications of a planar separator theorem. SIAM journal on computing\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM journal on computing"},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0213001","volume":"13","author":"N. Meggido","year":"1984","unstructured":"Meggido, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM journal on computing\u00a013, 1\u201329 (1984)","journal-title":"SIAM journal on computing"},{"key":"22_CR21","first-page":"538","volume-title":"32nd annual symposium on foundation of computer science","author":"G.L. Miller","year":"1991","unstructured":"Miller, G.L., Teng, S.-H., Vavasis, S.A.: An unified geometric approach to graph separators. In: 32nd annual symposium on foundation of computer science, pp. 538\u2013547. IEEE, Los Alamitos (1991)"},{"key":"22_CR22","first-page":"300","volume-title":"22nd Annual ACM symposium on theory of computing","author":"G.L. Miller","year":"1990","unstructured":"Miller, G.L., Thurston, W.: Separators in two and three dimensions. In: 22nd Annual ACM symposium on theory of computing, pp. 300\u2013309. ACM, New York (1990)"},{"issue":"5","key":"22_CR23","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0020-0190(87)90206-7","volume":"25","author":"S.S. Ravi","year":"1987","unstructured":"Ravi, S.S., Hunt III, H.B.: Application of the planar separator theorem to computing problems. Information processing letter\u00a025(5), 317\u2013322 (1987)","journal-title":"Information processing letter"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Smith, W.D., Wormald, N.C.: Application of geometric separator theorems. In: The 39th annual symposium on foundations of computer science, pp. 232\u2013243 (1998)","DOI":"10.1109\/SFCS.1998.743449"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.H.: Disk packings and planar separators. In: The 12th annual ACM symposium on computational geometry, pp. 349\u2013358 (1996)","DOI":"10.1145\/237218.237404"},{"key":"22_CR26","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial geometry","author":"J. Pach","year":"1995","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial geometry. Wiley-Interscience Publication, Chichester (1995)"},{"key":"22_CR27","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D.W. Wong","year":"1988","unstructured":"Wong, D.W., Kuo, Y.S.: A study of two geometric location problems. Information processing letters\u00a028, 281\u2013286 (1988)","journal-title":"Information processing letters"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T12:31:25Z","timestamp":1683376285000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/11672142_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}