Wiring Edge-Disjoint Layouts

Kuchem, Ruth and Wagner, Dorothea (1997) Wiring Edge-Disjoint Layouts. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 271-285 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_54).

Full text not available from this repository.

Abstract

We consider the wiring or layer assignment problem for edge-disjoint layouts. The wiring problem is well understood for the case that underlying layout graph is a square grid. In this paper, we introduce a more general approach to this problem. For an edge-disjoint layout in the plane resp. in an arbitrary planar layout graph, we give equivalent conditions for the k-layer wirability. Based on these conditions, we obtain linear-time algorithms to wire every layout in a tri-hexagonal grid, respectively every layout in a tri-square-hexagonal grid using at most five layers.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_54
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
ID Code:149

Repository Staff Only: item control page

References

M. Brady and D. Brown. VLSI routing: Four layers suffice. In F. Preparata, editor, Advances in Computer Research, vol. 2: VLSI Theory, JAI Press inc. (1984) 245-257.

M. Braddy and M. Sarrafzadeh. Stretching a knock-knee layout for multilayer wiring. IEEE Transactions on Computers, C-39 (1990) 148-152.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

T.F. Gonzales and S. Zheng. Simple three-layer channel routing algorithms. In J.H. Reif, editor, Proc. Aegean Workshop on Computing. Springer-Verlag, LNCS 319 (1988) 237-246.

M. Kaufmann and P. Molitor. Minimal stretching of a layout to ensure 2-layer wirability. Integration The VLSI journal, 12 (1991) 339-352.

R. Kuchem, D. Wagner, and F. Wagner. Optimizingarea for three-layer channel routing. Algorithmica, 15 (1996) 495-519.

W. Lipski Jr. On the structure of three-layer wirable layouts. In F. Preparata, editor, Advances in Computer Research, vol. 2: VLSI Theory, JAI Press inc. (1984) 231-243.

W. Lipski Jr. and F. Preparata. A unified approach to layout wirability. Math. Systems Theory, 19 (1987) 189-203.

R.H. Möhring, D. Wagner and F. Wagner. VLSI Network Design: A survey. In M. Ball, T. Magnanti, C. Monma, und G. Nemhauser, editors, Handbooks in Operation Rersearch/Management Science, vol. on Networks, North Holland, (1995) 625-712.

P. Molitor. A surwey on wiring. J. Inform. Process. Cybernet. EIK, 27 (1991) 3-19.

H. Ripphausen-Lipa, D. Wagner, and K. Weihe. Efficient algorithms for disjoint paths in planar graphs. In W. Cook, L. Lovász, and P. Seymour, editors, DIMACS Center for Discr. Math. and Comp. Sc., 20, Springer-Verlag, Berlin (1995) 295-354.

M. Sarrafzadeh, D. Wagner, F. Wagner, and K. Weihe. Wiring knock-knee layouts: a global approach. IEEE Transactiona on Computers 43 (1994) 581-589.

I.G. Tollis. Wiring layouts in the tri-hexagonal grid. Intern. J. Comput. Math. 37 (1990) 161-171.

I.G. Tollis. A new approach to wiring layouts. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 10 (1991) 1392-1400.

I.G. Tollis. Wiring in uniform grids and two-colorable maps. Integration The VLSI journal, 12 (1991) 189-210.

D. Wagner. Optimal routing through dense channels. Int. J. on Comp. Geom. and Appl. 3 (1993) 269-289.