Kaufmann, Michael; Mehlhorn, Kurt On local routing of two-terminal nets. (English) Zbl 0810.05063 J. Comb. Theory, Ser. B 55, No. 1, 33-72 (1992). Summary: We examine the problem of finding edge-disjoint paths between pairs of vertices placed on inner as well as outer faces of a finite grid graph. For each path a global routing, which fixes the topology of the path relative to the nontrivial faces, is part of the input. We give necessary and sufficient conditions for the solvability of the problem and provide an algorithm to find a solution with running time quadratic in the size of the problem. Cited in 2 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles 90C35 Programming involving graphs or networks 68R10 Graph theory (including graph drawing) in computer science Keywords:local routing; edge-disjoint paths; faces; finite grid graph; routing; algorithm PDFBibTeX XMLCite \textit{M. Kaufmann} and \textit{K. Mehlhorn}, J. Comb. Theory, Ser. B 55, No. 1, 33--72 (1992; Zbl 0810.05063) Full Text: DOI References: [1] Brady, M.; Brown, D., VLSI routing: Four layers suffice, Adv. Comput. Res., 2, 245-258 (1984) [2] Becker, M.; Mehlhorn, K., Algorithms for routing in planar graphs, Acta Inform., 23, 163-176 (1986) · Zbl 0591.68065 [3] R. Cole and A. Siegelin; R. Cole and A. Siegelin [4] Frank, A., Disjoint paths in rectilinear grids, Combinatorica, 2, No. 4, 361-371 (1982) · Zbl 0515.05044 [5] van Hoesel, C.; Schrijver, A., Edge-disjoint homotopic paths in a planar graph with one hole, J. Combin. Theory Ser. B, 48, 77-91 (1990) · Zbl 0636.05035 [6] Kaufmann, M., Über lokales Verdrahten von 2-Punkt-Netzen, (Dissertation (1987), Universität des Saarlandes) [7] Kaufmann, M.; Mehlhorn, K., Routing through a generalized switchbox, J. Algorithms, 7, 510-531 (1986) · Zbl 0631.68062 [8] Kaufmann, M.; Mehlhorn, K., A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs (1988), Technical Report, Saarbrücken [9] Kramer, M. E.; van Leeuwen, J., The complexity of wire routing and finding minimum area layouts for arbitrary VLSI circuits, Adv. Comput., 2, 129-146 (1984) [10] Lauther, U., The SIEMENS CALCOS system for computer aided design of cell based IC layout, (Proceedings, 1st ICCC (1980)), 768-771, Proc [11] Leiserson, Ch; Maley, F. M., Algorithms for routing and testing routability of planar VLSI layouts, (17th STOC (1985)), 69-78 [12] Matsumoto, K.; Nishizeki, T.; Saito, N., An efficient algorithm for finding multicommodity flows in planar networks, SICOMP, Vol. 15, No. 2, 495-510 (1986) · Zbl 0592.05024 [13] Mehlhorn, K.; Preparata, F., Routing through a rectangle, J. Assoc. Comput. Mach., 33, 60-85 (1986) [14] Nishizeki, T.; Saito, N.; Suzuki, K., A linear-time routing algorithm for convex grids, IEEE Trans. Comput. Aided Design, CAD-4, 68-76 (1985) [15] Okamura, H.; Seymour, P. D., Multicommodity flows in planar graphs, J. Combin. Theory Ser. B, 31, 75-81 (1981) · Zbl 0465.90029 [16] Preparata, F.; Lipski, W., Three layers are enough, 23rd Found. Comput. Sci., 350-357 (1982) [17] Rivest, R. L., The “PI” (placement and interconnect) system, (19th Design Automation Conference (1982)), 475-481 [18] Sarrafzadeh, M., Channel-routing problem in knock-knee mode is NP-complete, IEEE Trans. Comput. Aided Design, CAD-6, 503-506 (1987) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.