zbMATH — the first resource for mathematics

Simple and efficient floor-planning. (English) Zbl 1173.68768
Summary: We show a new algorithm for computing in \(O(n)\) time a floor-plan of a given plane near-triangulation. We use modules which are the union of two rectangles and are T-, L- or I-shaped. Our algorithm has the following advantages: the number of T-shaped modules is at most \(\frac{1}{2}(n-2)\), all T-shaped modules are uniformly directed, the size of the picture is at most \(n\times n - 1\). A very important asset of our algorithm is its extraordinary simplicity.

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W05 Nonnumerical algorithms
Full Text: DOI
[1] Bhasker, J.; Sahni, S., A linear algorithm to check for the existence of a rectangular dual of planar triangulated graph, Networks, 17, 307-317, (1987) · Zbl 0672.05025
[2] Bhasker, J.; Sahni, S., A linear algorithm to find for a rectangular dual of planar triangulated graph, Algorithmica, 3, 247-278, (1988) · Zbl 0635.68074
[3] Liao, C.-C.; Lu, H.-I; Yen, H.-C., Floor-planning via orderly spanning trees, () · Zbl 1054.68597
[4] C.-C. Liao, H.-I Lu, H.-C. Yen, Personal communication
[5] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I.G., Algorithms for drawing graphs: an annotated bibliography, Comput. geom. theory appl., 4, 235-282, (1994) · Zbl 0804.68001
[6] de Fraysseix, H.; Pach, J.; Pollack, R., Small sets supporting fary embedding of planar graphs, (), 426-433
[7] Kozminski, K.; Kinnen, E., Rectangular duals of planar graphs, Networks, 15, 145-157, (1985) · Zbl 0585.05029
[8] Kozminski, K.; Kinnen, E., Rectangular dualization and rectangular dissection, IEEE trans. circuits systems, 35, 1401-1416, (1988) · Zbl 0663.05027
[9] Mailing, K.; Mueller, S.H.; Heller, W.R., On finding most optimal rectangular package plans, (), 263-270
[10] Lai, Y.T.; Leinwand, S.M., A theory of rectangular dual graphs, Algorithmica, 5, 467-483, (1990) · Zbl 0712.05053
[11] Yeap, Y-H.; Sarrafzadeh, M., Floor-planning by graph dualization: 2-concave rectilinear modules, SIAM J. comput., 22, 3, 500-526, (1993) · Zbl 0774.05093
[12] Sun, Y.; Sarrafzadeh, M., Floor-planning by graph dualization: L-shaped models, (), Algorithmica, 10, 429-456, (1993) · Zbl 0780.94019
[13] He, X., On floorplans of planar graphs, (), 426-435 · Zbl 0963.68151
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.