{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T05:17:33Z","timestamp":1672723053946},"reference-count":7,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1986,1,2]]},"abstract":"\n In this paper an\n O<\/jats:italic>\n (\n N<\/jats:italic>\n log\n N<\/jats:italic>\n ) algorithm for routing through a rectangle is presented. Consider an\n n<\/jats:italic>\n -by-\n m<\/jats:italic>\n rectangular grid and a set of\n N<\/jats:italic>\n two-terminal nets. A net is a pair of points on the boundary of the rectangle. A layout is a set of edge-disjoint paths, one for each net. Our algorithm constructs a layout, if there is one, in\n O<\/jats:italic>\n (\n N<\/jats:italic>\n log\n N<\/jats:italic>\n ) time; this contrasts favorably with the area of the layout that might be as large as\n N<\/jats:italic>\n 2<\/jats:sup>\n . The layout constructed can be wired using four layers of interconnect with only\n O<\/jats:italic>\n (\n N<\/jats:italic>\n ) contact cuts. A partial extension to multiterminal nets is also discussed.\n <\/jats:p>","DOI":"10.1145\/4904.4994","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"60-85","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Routing through a rectangle"],"prefix":"10.1145","volume":"33","author":[{"given":"K.","family":"Mehlhorn","sequence":"first","affiliation":[{"name":"Univ. des Saarlandes, Saarbru\u00a8cken, W. Germany"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[{"name":"Univ. of Illinois at Urbana-Champaign, Urbana"}]}],"member":"320","published-online":{"date-parts":[[1986,1,2]]},"reference":[{"key":"e_1_2_1_1_2","volume-title":"Solution to Klee's rectangle problems. Unpublished notes","author":"BENTLEY J. L.","year":"1977","unstructured":"BENTLEY , J. L. Solution to Klee's rectangle problems. Unpublished notes . Carnegie-Mellon University , Pittsburgh, Pa ., 1977 . BENTLEY, J. L. Solution to Klee's rectangle problems. Unpublished notes. Carnegie-Mellon University, Pittsburgh, Pa., 1977."},{"key":"e_1_2_1_2_2","volume-title":"VLSI routing: Four layers suffice. Adv. Comput. Res. 2: VLS! Theory","author":"BRADY M.","year":"1984","unstructured":"BRADY , M. , AND BROWN , D.J. VLSI routing: Four layers suffice. Adv. Comput. Res. 2: VLS! Theory ( 1984 ), 245-257. BRADY, M., AND BROWN, D.J. VLSI routing: Four layers suffice. Adv. Comput. Res. 2: VLS! Theory (1984), 245-257."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02579432","volume":"2","author":"FRANK A.","unstructured":"FRANK , A. Disjoint paths in a rectilinear grid. Combinatorica 2 , 4 (I982), 361 - 337 i. FRANK, A. Disjoint paths in a rectilinear grid. Combinatorica 2, 4 (I982), 361-37 i.","journal-title":"Combinatorica"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0196-6774(80)90011-5","volume":"1","author":"LIPSKI W.","year":"1980","unstructured":"LIPSKI , W. , JR ., AND PREPARATA , F.P. Finding the contour of a union ofiso-oriented rectangles. J. Alg. 1 ( 1980 ), 235 - 246 . LIPSKI, W., JR., AND PREPARATA, F.P. Finding the contour of a union ofiso-oriented rectangles. J. Alg. 1 (1980), 235-246.","journal-title":"J. Alg."},{"key":"e_1_2_1_5_2","volume-title":"Priority search trees. Res. Rep. CSL-81-5","author":"MCCREIGHT E. M.","year":"1982","unstructured":"MCCREIGHT , E. M. Priority search trees. Res. Rep. CSL-81-5 . Xerox Corporation , Palo Alto , Calif., January 1982 . MCCREIGHT, E. M. Priority search trees. Res. Rep. CSL-81-5. Xerox Corporation, Palo Alto, Calif., January 1982."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676459"},{"key":"e_1_2_1_7_2","first-page":"15","volume-title":"Proceedings of the CMU Conference on VLSI Systems and Computations","author":"VEST R. L.","unstructured":"Ri VEST , R. L. , BARATZ , A. E. , AND MILLER , G. Provably good channel routing algorithms . In Proceedings of the CMU Conference on VLSI Systems and Computations ( Pittsburgh, Oct. 19-21). Computer Science Press, Rockville, Md., 198 l , pp. 15 l- 159. RiVEST, R. L., BARATZ, A. E., AND MILLER, G. Provably good channel routing algorithms. In Proceedings of the CMU Conference on VLSI Systems and Computations (Pittsburgh, Oct. 19-21). Computer Science Press, Rockville, Md., 198 l, pp. 15 l- 159."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/4904.4994","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T18:47:47Z","timestamp":1672685267000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/4904.4994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1,2]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1986,1,2]]}},"alternative-id":["10.1145\/4904.4994"],"URL":"https:\/\/doi.org\/10.1145\/4904.4994","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1,2]]},"assertion":[{"value":"1986-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}