{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T05:34:40Z","timestamp":1735882480572,"version":"3.32.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1996,1]]},"DOI":"10.1007\/bf01942604","type":"journal-article","created":{"date-parts":[[2005,7,26]],"date-time":"2005-07-26T20:24:55Z","timestamp":1122409495000},"page":"1-16","source":"Crossref","is-referenced-by-count":2,"title":["Testing homotopic routability under polygonal wiring rules"],"prefix":"10.1007","volume":"15","author":[{"given":"F. M.","family":"Maley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01942604_CR1","unstructured":"S.-C. Chang, J. J\u00e1J\u00e1, and K. W. Ryu, Optimal parallel algorithms for one-layer routing, UMIACS Technical Report TR-89-46, University of Maryland, 1989."},{"key":"BF01942604_CR2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02187743","volume":"4","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension,Discrete and Computational Geometry,4 (1989), 467\u2013489.","journal-title":"Discrete and Computational Geometry"},{"key":"BF01942604_CR3","doi-asserted-by":"crossref","unstructured":"R. Cole and A. Siegel, River routing every which way, but loose,Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984, pp. 65\u201373.","DOI":"10.1109\/SFCS.1984.715902"},{"key":"BF01942604_CR4","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. R\u00fclling, and C. Storb, On continuous homotopic one layer routing,Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988, pp. 392\u2013402.","DOI":"10.1145\/73393.73433"},{"key":"BF01942604_CR5","doi-asserted-by":"crossref","unstructured":"S. Gao, M. Kaufmann, and F. M. Maley, Advances in homotopic layout compaction,Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 273\u2013282.","DOI":"10.1145\/72935.72964"},{"issue":"4","key":"BF01942604_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(92)90201-6","volume":"43","author":"R. I. Greenberg","year":"1992","unstructured":"R. I. Greenberg and F. M. Maley, Minimum separation for single-layer channel routing,Information Processing Letters,43(4) (1992), 201\u2013205.","journal-title":"Information Processing Letters"},{"issue":"1","key":"BF01942604_CR7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF01185338","volume":"9","author":"M. Kaufmann","year":"1993","unstructured":"M. Kaufmann and F. M. Maley, Parity conditions in homotopic knock-knee routing,Algorithmica,9(1) (1993), 47\u201363.","journal-title":"Algorithmica"},{"key":"BF01942604_CR8","unstructured":"M. Kaufmann and F. M. Maley, Computing congestion during one-dimensional homotopic compaction,Journal of Algorithms, to appear."},{"issue":"1","key":"BF01942604_CR9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0095-8956(92)90031-R","volume":"55","author":"M. Kaufmann","year":"1992","unstructured":"M. Kaufmann and K. Mehlhorn, On local routing of 2-terminal nets,Journal of Combinatorial Theory Series B,55(1) (1992), 33\u201372.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"BF01942604_CR10","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson and F. M. Maley, Algorithms for routing and testing routability of planar VLSI layouts,Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 69\u201378.","DOI":"10.1145\/22145.22153"},{"key":"BF01942604_CR11","doi-asserted-by":"crossref","unstructured":"F. M. Maley, Toward a mathematical theory of single-layer wire routing,Proceedings of the Fifth MIT Conference on Advanced Research in VLSI, 1988, pp. 277\u2013296.","DOI":"10.7551\/mitpress\/1102.003.0023"},{"key":"BF01942604_CR12","volume-title":"Single-Layer Wire Routing and Compaction","author":"F. M. Maley","year":"1990","unstructured":"F. M. Maley,Single-Layer Wire Routing and Compaction, MIT Press, Cambridge, MA, 1990."},{"issue":"1","key":"BF01942604_CR13","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/BF01759037","volume":"6","author":"F. M. Maley","year":"1991","unstructured":"F. M. Maley, A generic algorithm for one-dimensional homotopic compaction,Algorithmica,6(1) (1991), 103\u2013128.","journal-title":"Algorithmica"},{"issue":"2","key":"BF01942604_CR14","first-page":"103","volume":"25","author":"J. Matou\u0161ek","year":"1991","unstructured":"J. Matou\u0161ek, Spanning trees with low crossing number,RAIRO: Informatique Theoretique et Applications,25(2) (1991), 103\u2013123.","journal-title":"RAIRO: Informatique Theoretique et Applications"},{"issue":"2","key":"BF01942604_CR15","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"E. M. McCreight, Priority search trees,SIAM Journal on Computing,14(2) (1985), 257\u2013276.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"BF01942604_CR16","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/43.46782","volume":"9","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her, A faster compaction algorithm with automatic jog insertion,IEEE Transactions on CAD,9(2) (1990), 158\u2013166.","journal-title":"IEEE Transactions on CAD"},{"key":"BF01942604_CR17","unstructured":"R. Y. Pinter, The Impact of Layer Assignment Methods on Layout Algorithms for Integrated Circuits, Ph.D. Thesis, EECS Department, MIT, 1982."},{"key":"BF01942604_CR18","first-page":"141","volume-title":"River routing: methodology and analysis","author":"R. Y. Pinter","year":"1983","unstructured":"R. Y. Pinter, River routing: methodology and analysis,Proceedings of the Third Caltech Conference on VLSI, Computer Science Press, Rockville, MD, 1983, pp. 141\u2013163."},{"key":"BF01942604_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"issue":"7","key":"BF01942604_CR20","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan, Planar point location using persistent search trees,Communications of the ACM,29(7) (1986), 669\u2013679.","journal-title":"Communications of the ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942604.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01942604\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T18:19:57Z","timestamp":1735841997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01942604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF01942604"],"URL":"https:\/\/doi.org\/10.1007\/bf01942604","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}