Rectilinear Steiner trees on a checkerboard

ABSTRACT

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a fully-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing the performance of this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms, based on geometric partitioning, global routing of field-programmable gate arrays, and routing estimation during floorplanning.

REFERENCES

• 1: AHO, A. V., GAREY, M. R., AND HWANG, F. K. 1977. Rectilinear Steiner trees: Efficient special-case algorithms. Networks 7, 37-58.
• 2: Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, Performance-oriented placement and routing for field-programmable gate arrays, Proceedings of the conference on European design automation, p.80-85, September 18-22, 1995, Brighton, England
• 3: BAPAT, S. AND COHOON, J.P. 1993. A parallel VLSI circuit layout methodology. In Proceedings of the Sixth International Conference on VLSI Design (Bapat, India, Jan.), 236-241.
• 4: M. Brazil , T. Cole , J. H. Rubinstein , D. A. Thomas , J. F. Weng , N. C. Wormald, Minimal Steiner trees for 2k×2k square lattices, Journal of Combinatorial Theory Series A, v.73 n.1, p.91-110, Jan. 1996 [doi>10.1006/jcta.1996.0004]
• 5: BRAZIL, M., RUBINSTEIN, J. H., THOMAS, D. A., WENG, J. F., AND WORMALD, N.C. 1995. Full minimal Steiner trees on lattice sets. Tech. Rep. 14-1995, Dept. of Mathematics, Univ. of Melbourne, Victoria, Australia.
• 6: CHUNG, F. R. K., GARDNER, M., AND GRAHAM, R.L. 1989. Steiner trees on a checkerboard. Math. Mag. 62, 83-96.
• 7: CHUNG, F. R. K. AND GRAHAM, R.L. 1978. Steiner trees for ladders. Ann. Discrete Math. 2, 173-200.
• 8: E J Cockayne , D E Hewgill, Exact computation of Steiner Minimal Trees in the plane, Information Processing Letters, v.22 n.3, p.151-156, March 1986 [doi>10.1016/0020-0190(86)90062-1]
• 9: COCKAYNE, E. g. AND HEWGILL, D.E. 1992. Improved computation of plane Steiner minimal trees. Algorithmica 7, 219-229.
• 10: DREYFUS, S. E. AND WAGNER, R. A. 1972. The Steiner problem in graphs. Networks 1, 195-207.
• 11: EPPSTEIN, D., GALIL, Z., ITALIANO, G. F., AND NISSENZWEIG, A. 1992. Sparsification: A technique for speeding up dynamic graph algorithms. In Proceedings of the 33rd Symposium on Foundations of Computer Science (Pittsburgh, PA, Oct.), 60-69.
• 12: Joseph Lavinus Ganley, Geometric interconnection and placement algorithms, 1995
• 13: GANLEY, J. L. AND COHOON, J.P. 1994a. A faster dynamic programming algorithm for exact rectilinear Steiner minimal trees. In Proceedings of the Fourth Great Lakes Symposium on VLSI (South Bend, IN, March), 238-241.
• 14: GANLEY, J. L. AND COHOON, J. P. 1994b. Optimal rectilinear Steiner minimal trees in 0(n22.62n) time. In Proceedings of the Sixth Canadian Conference on Computational Geometry (Saskatoon, Sask., Aug.), 308-313.
• 15: J. L. Ganley , J. P. Cohoon, Thumbnail rectilinear Steiner trees, Proceedings of the Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), p.46, March 16-18, 1995
• 16: GAREY, M. R. AND JOHNSON, D.S. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826-834.
• 17: HAKIMI, S.L. 1971. Steiner's problem in graphs and its implications. Networks 1, 113-133.
• 18: HANAN, M. 1966. On Steiner's problem with rectilinear distance. SIAM J. Appl. Math. 14, 255-265.
• 19: HWANG, F. K. 1976. On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 104-114.
• 20: HWANG, F. K. AND DU, D. Z. 1991. Steiner minimal trees on the Chinese checkerboard. Math. Mag. 64, 332-339.
• 21: KREWERAS, G. 1978. Complexit~ et circuits Eul~riens dan les sommes tensorielles de graphes. J. Comb. Theor., Series B 24, 202-212.
• 22: MAYRHOFER, S. AND LAUTHER, U. 1990. Congestion-driven placement using a new multipartitioning heuristic. In Proceedings of the International Conference on Computer-Aided Design (Santa Clara, CA, Nov.), 332-335.
• 23: RICHARDS, D. S. AND SALOWE, J.S. 1991. A simple proof of Hwang's theorem for rectilinear Steiner minimal trees. Ann. Oper. Res. 33, 549-556.
• 24: SALOWE, J. S. AND WARME, D.M. 1995. 35-point rectilinear Steiner minimal trees in a day. Networks 25, 69-87.
• 25: SUARIS, P. R. AND KEDEM, G. 1989. A quadrisection-based place and route scheme for standard cells. IEEE Trans. Comput. Aided Des. 8, 234-244.
• 26: WINTER, P. 1985. An algorithm for the Steiner problem in the Euclidean plane. Networks 15, 323-345.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory

Keywords:
exact algorithms, full-set decomposition, rectilinear Steiner tree, routing