{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:47Z","timestamp":1725559007194},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_22","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"248-259","source":"Crossref","is-referenced-by-count":1,"title":["Subexponential-Time Framework for Optimal Embeddings of Graphs in Integer Lattices"],"prefix":"10.1007","author":[{"given":"Anders","family":"Dessmark","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Lingas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eva-Marta","family":"Lundell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Seymour, P., Thomas, R.: A separator Theorem for Graphs with an Excluded Minor and its Applications. In: 22nd ACM STOC, pp. 293\u2013299 (1990)","DOI":"10.1145\/100216.100254"},{"issue":"5","key":"22_CR2","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial-time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"22_CR3","volume-title":"Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin (1999)"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Berger, B., Leighton, T.: Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete. In: Proc. RECOMB 1998, New York, pp. 30\u201339 (1998)","DOI":"10.1089\/cmb.1998.5.27"},{"issue":"3","key":"22_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1089\/cmb.1998.5.423","volume":"5","author":"P. Crescenzi","year":"1998","unstructured":"Crescenzi, P., Goldman, D., Papadimitriou, C.H., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding. Journal of Computational Biology\u00a05(3), 423\u2013466 (1998)","journal-title":"Journal of Computational Biology"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1021\/bi00327a032","volume":"24","author":"K.A. Dill","year":"1985","unstructured":"Dill, K.A.: Theory for the folding and stability of globular proteins. Biochemistry\u00a024, 1501 (1985)","journal-title":"Biochemistry"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Miller, G.L., Teng, S.-H.: A deterministic linear time algorithm for geometric separators and its applications. In: Proc. Symposium on Computational Geometry, pp. 99\u2013108 (1993)","DOI":"10.1145\/160985.161005"},{"key":"22_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/3-540-53832-1_38","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Formann","year":"1991","unstructured":"Formann, M., Wagner, F.: The VLSI layout problem in various embedding models. In: M\u00f6hring, R.H. (ed.) WG 1990. LNCS, vol.\u00a0484, pp. 130\u2013139. Springer, Heidelberg (1991)"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Hart, W.E., Istrail, S.: Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal. In: 27th annual ACM Symposium on Theory of Computing, pp. 157\u2013168 (1995)","DOI":"10.1145\/225058.225106"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Leighton, F.T.: New Lower Bound Techniques for VLSI. In: Proc. 22nd Annual Symposium on Foundations of Computer Science, pp. 1\u201312 (1981)","DOI":"10.1109\/SFCS.1981.22"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: FOCS, pp. 270\u2013281 (1980)","DOI":"10.1109\/SFCS.1980.13"},{"issue":"2","key":"22_CR12","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.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"22_CR13","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"G.L. Miller","year":"1998","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Geometric separators for finite-element meshes. SIAM J. Sci. Comput.\u00a019(2), 364\u2013386 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"22_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for spherepackings and nearest neighbor graphs. Journal of the ACM\u00a044(1), 1\u201329 (1997)","journal-title":"Journal of the ACM"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Teng, S.-H., Vavasis, S.A.: A unified geometric approach to graph separators. In: Proc. 31st Annual Symposium on Foundations of Computer Science, pp. 538\u2013547 (1991)","DOI":"10.1109\/SFCS.1991.185417"},{"key":"22_CR16","unstructured":"Nayak, A.: Spatial codes and the hardness of string folding problems (extended abstract). In: Proc. Symposium on Discrete Algorithms, pp. 639\u2013648 (1998)"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-24587-2_2","volume-title":"Algorithms and Computation","author":"T. Nishizeki","year":"2003","unstructured":"Nishizeki, T.: Drawing plane graphs. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 2\u20135. Springer, Heidelberg (2003)"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1007\/3-540-61440-0_167","volume-title":"Automata, Languages and Programming","author":"M.S. Paterson","year":"1996","unstructured":"Paterson, M.S., Przytycka, T.M.: On the complexity of string folding. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 658\u2013669. Springer, Heidelberg (1996)"},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"Patrignani, M.: On the Complexity of Orthogonal Compaction. In: Workshop on Algorithms and Data Structures, pp. 56\u201361 (1999)","DOI":"10.1007\/3-540-48447-7_7"},{"key":"22_CR20","unstructured":"Raghavan, P.: Line and plane separators. Technical Report UIUCDCS-R-93-1794 (1993)"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Storer, J.A.: The node cost measure for embedding graphs on the planar grid. In: Proc. 12th annual ACM Symposium on Theory of Computing, pp. 201\u2013210 (1980)","DOI":"10.1145\/800141.804667"},{"issue":"3","key":"22_CR22","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"Tamassia, R.: On Embedding a Graph in the Grid with the Minimum Number of Bends. SIAM J. Comput.\u00a016(3), 421\u2013444 (1987)","journal-title":"SIAM J. Comput."},{"key":"22_CR23","volume-title":"Computational Aspects of VLSI","author":"J.D. Ullman","year":"1984","unstructured":"Ullman, J.D.: Computational Aspects of VLSI. Computer Science Press, Rockville (1984)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:42Z","timestamp":1605759702000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}