Floor-Planning via Orderly Spanning Trees

Liao, Chien-Chih and Lu, Hsueh-I. and Yen, Hsu-Chun (2002) Floor-Planning via Orderly Spanning Trees. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 367-377 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_29).

Full text not available from this repository.

Abstract

Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size (n-1)\times \left\lfloor\frac{2n+1}{3}\right\rfloor.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_29
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
ID Code:527

Repository Staff Only: item control page

References

J. Bhasker and S. Sahni. A linear algorithm to check for the existance of a rectangular dual of a planar triangulated graph. Networks, 17:307-317, 1987.

J. Bhasker and S. Sahni. A linear algorithm to find a rectangular dual of a planar triangulated graph. Algorithmica 3:247-278, 1988.

Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 506-515, Washington D.C., USA,7-9 Jan. 2001. A revised and extended version can be found at http://xxx.lanl.gov/abs/cs.DS/0102006.

R.C.-N. Chuang, A. Garg, X. He, M.-Y. Kao, and H.-I. Lu. Compact encodings of planar graphs via canonical ordering and multiple parenthese. In K.G. Larsen, S. Skyum, and G. Winskel, editors, Proceedings of the 25th International Colloquium on Automata, Languages and Programming, LNCS 1443, pages 118-129, Aalborg, Denmark, 1998. Springer-Verlag.

H. de Fraysseix, P. Ossona de Medez, and P. Rosenstiehl, On triangle contact graphs, Combinatorics, Probability and Computing 3 (1994), 233-246.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

U. Fößmeier, G. Kant, and M. Kaufmann. 2-Visibility drawings of planar graphs. In S. North,ed., Symposium on Graph Drawing 96, vol. 1190 of LNCS, Springer-Verlag, 1996, pages 155-168.

X. He. On finding the rectangular duals of planar triangular graphs. SIAM Journal on Computing, 22:1218-1226, 1993.

X. He. On floor-plan af plane graphs. SIAM Journal on Computing, 28(6):2150-2167, 1999.

G. Jacobson. Space-efficient static trees and graphs. In Proceedings of the 30th Annual Symposium on Foundation of Computer Science, pages 549-554, Research Triangle Park, North Carolina, 30 Oct. - 1 Nov. 1989, IEEE.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996. (Special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Cpmputer Science, 172(1-2):175-193, 1997.

K. Kozminski and E. Kinnen. Rectangular duals of planar graphs. Networks, 15(2):145-157, 1985.

K. Kozminski and E. Kinnen. Rectangular dualization and rectangular dissections. IEEE Transactions on Circuits and Systems, 35(11):1401-1416, 1988.

Y.T. Lai and S.M. Leinwand. A theory of rectangular dual graphs. Algoritmica 5(4):467-483, 1990.

K. Mailing, S.H. Mueller, and W.R. Heller. On finding most optimal rectangular package plans. In Proceedings of the 19th Annual IEEE Design Automation Conference, pages 263-270, 1982.

J.I. Munro and V. Raman. Succinct representation of balanced parenthese, static trees and planar graphs. In Proc. of the 38th Annual Symposium on Foundations of Computer Science, pages 118-126, Miami Beach, Florida, 20-22 Oct. 1997. IEEE.

W. Schnyder, Planar graphs and poset dimension, Order 5 (1989), 323-343.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.

S. Tsukiyama, K. koike, and I. Shirakawa. An algorithm to eliminate all complex triangles in a maximal planar graph for use in VLSI floorplan. In Proc. of the IEEE International Symposium on Circuits and Systems, pages 321-324, 1986.

K.-H. Yeap and M. Sarrafzadeh. Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM Journal on Computing, 22(3):500-526, 1993.