{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:21Z","timestamp":1750308201698,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>The maze routing problem is to find an optimal path between a given pair of cells on a grid plane. Lee's algorithm and its variants, probably the most widely used maze routing method, fails to work in the 4-geometry of the grid plane. Our algorithm solves this problem by using a suitable data structure for uniform wave propagation in the 4-geometry, 8-geometry, etc. The algorithm guarantees finding an optimal path if it exists and has linear time and space complexities. Next, to solve the obstacle-avoiding rectilinear and 4-geometry Steiner tree problems, a heuristic algorithm is presented. The algorithm utilizes a cost accumulation scheme based on the maze router to determine the Torricelli vertices (points) for improving the quality of multiterminal nets. Our experimental results show that the algorithm works well in practice. Furthermore, using the 4-geometry router, path lengths can be significantly reduced up to 12% compared to those in the rectilinear router.<\/jats:p>","DOI":"10.1145\/1044111.1044118","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"116-135","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A 4-geometry maze router and its application on multiterminal nets"],"prefix":"10.1145","volume":"10","author":[{"given":"Gene Eu","family":"Jan","sequence":"first","affiliation":[{"name":"National Taipei University, Sun Shia, Taipei"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ki-Yin","family":"Chang","sequence":"additional","affiliation":[{"name":"National Taiwan Ocean University, Keelung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Su","family":"Gao","sequence":"additional","affiliation":[{"name":"University of North Texas, Denton, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"Parberry","sequence":"additional","affiliation":[{"name":"University of North Texas, Denton, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77615"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01592245"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1080\/02331939108843669"},{"volume-title":"Steiner Minimal Trees","author":"Cieslik D.","key":"e_1_2_1_5_1","unstructured":"Cieslik , D. 1998. Steiner Minimal Trees , Kluwer Academic Publishers , Dordrecht, The Netherlands.]] Cieslik, D. 1998. Steiner Minimal Trees, Kluwer Academic Publishers, Dordrecht, The Netherlands.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/3477.678654"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume-title":"Institute for System Studies","author":"Dinic E. A.","key":"e_1_2_1_8_1","unstructured":"Dinic , E. A. 1978. Economical algorithms for finding shortest paths in a network , In Transportation Modeling Systems, Y. S. Popkov and B. L. Shmulyian, Eds. Institute for System Studies , Moscow, Russia , 36--44.]] Dinic, E. A. 1978. Economical algorithms for finding shortest paths in a network, In Transportation Modeling Systems, Y. S. Popkov and B. L. Shmulyian, Eds. Institute for System Studies, Moscow, Russia, 36--44.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008285504599"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.844372"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems","volume":"1","author":"Ganley J. L.","unstructured":"Ganley , J. L. and Cohoon , J. P . 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles . Proceedings of the IEEE International Symposium on Circuits and Systems , vol. 1 . 113--116.]] Ganley, J. L. and Cohoon, J. P. 1994. Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles. Proceedings of the IEEE International Symposium on Circuits and Systems, vol. 1. 113--116.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90032-0"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Simple shortest path algorithm with linear average time. Proceedings of the European Symposium on Algorithms (ESA)","author":"Goldberg A. V.","unstructured":"Goldberg , A. V. 2001. Simple shortest path algorithm with linear average time. Proceedings of the European Symposium on Algorithms (ESA) . Lecture Notes in Computer Science , Vol. 2161 . Springer-Verlag , Berlin Germeny , 230--241.]] Goldberg, A. V. 2001. Simple shortest path algorithm with linear average time. Proceedings of the European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, Vol. 2161. Springer-Verlag, Berlin Germeny, 230--241.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1493"},{"key":"e_1_2_1_16_1","first-page":"19","article-title":"Some variations of Lee's algorithm","volume":"1","author":"Joel J. H.","year":"1976","unstructured":"Joel , J. H. 1976 . Some variations of Lee's algorithm . IEEE Trans. Comput. C-25 , 1 ( Jan. ), 19 -- 24 .]] Joel, J. H. 1976. Some variations of Lee's algorithm. IEEE Trans. Comput. C-25, 1 (Jan.), 19--24.]]","journal-title":"IEEE Trans. Comput. C-25"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1979.1084551"},{"key":"e_1_2_1_18_1","first-page":"95","article-title":"Computerized shortest path searching for vessels","volume":"5","author":"Jan G. E.","year":"1997","unstructured":"Jan , G. E. , Lin , M. B. , and Chen , Y. Y. 1997 . Computerized shortest path searching for vessels . J. Marine Sci. Tech. 5 , 1, 95 -- 99 .]] Jan, G. E., Lin, M. B., and Chen, Y. Y. 1997. Computerized shortest path searching for vessels. J. Marine Sci. Tech. 5, 1, 95--99.]]","journal-title":"J. Marine Sci. Tech."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.144853"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.387512"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584648"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1961.5219222"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1976.1084243"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.46781"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(95)00059-3"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1974.224054"},{"volume-title":"3rd. ed","author":"Sherwani N. A.","key":"e_1_2_1_27_1","unstructured":"Sherwani , N. A. 1999. Algorithms for VLSI Physical Design Automation , 3rd. ed . Kulwer Academic Publishers , Boston, MA , 260--279.]] Sherwani, N. A. 1999. Algorithms for VLSI Physical Design Automation, 3rd. ed. Kulwer Academic Publishers, Boston, MA, 260--279.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction","author":"Teig S. L.","year":"2002","unstructured":"Teig , S. L. 2002 . The X architecture: Not your father's diagonal wiring . In Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction ( San Diego, CA, Apr. 6--7), ACM Press, New York, NY, 33--37.]] 10.1145\/505348.505355 Teig, S. L. 2002. The X architecture: Not your father's diagonal wiring. In Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction (San Diego, CA, Apr. 6--7), ACM Press, New York, NY, 33--37.]] 10.1145\/505348.505355"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/316542.316548"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90092-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.980255"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044111.1044118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:25:05Z","timestamp":1750263905000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044111.1044118"],"URL":"https:\/\/doi.org\/10.1145\/1044111.1044118","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}