Linear-time construction of floor plans for plane triangulations

[1] M.R. Akbari Jokar and A.S. Sangchooli, Constructing a block layout by face area, The International Journal of Advanced Manufacturing Technology 54 (2011), no. 5-8, 801–809.

[2] M.J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S.G. Kobourov, and T. Ueckerdt, Computing cartograms with optimal complexity, Discrete Comput. Geom. 50 (2013), no. 3, 784–810.

[3] I. Baybars and C.M. Eastman, Enumerating architectural arrangements by generating their underlying graphs, Environment and Planning B: Planning and Design 7 (1980), no. 3, 289–310.

[4] J. Bhasker and S. Sahni, A linear time algorithm to check for the existence of a rectangular dual of a planar triangulated graph, Networks 17 (1987), no. 3, 307–317.

[5] J. Bhasker and S. Sahni, A linear algorithm to find a rectangular dual of a planar triangulated graph, Algorithmica 3 (1988), no. 2, 247–278.

[6] T. Biedl and G. Kant, A better heuristic for orthogonal graph drawings, Comput. Geom. 9 (1998), no. 3, 159–180.

[7] Y.-J. Chang and H.-C. Yen, Rectilinear duals using monotone staircase polygons, International Conference on Combinatorial Optimization and Applications, Springer, 2014, pp. 86–100.

[8] M. De Berg, E. Mumford, and B. Speckmann, On rectilinear duals for vertex-weighted plane graphs, Discrete Math. 309 (2009), no. 7, 1794–1812.

[9] A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing, International Symposium on Graph Drawing, Springer, 1996, pp. 201–216.

[10] J.W. Giffin, K. Watson, and L.R. Foulds, Orthogonal layouts using the deltahedron heuristic., Australas. J. Combin. 12 (1995), 127–144.

[11] J.L. Gross and J. Yellen, Graph theory and its applications, CRC press, 2005.

12] X. He, On finding the rectangular duals of planar triangular graphs, SIAM J. Comput. 22 (1993), no. 6, 1218–1226.

[13] X. He, On floor-plan of plane graphs, SIAM J. Comput. 28 (1999), no. 6, 2150–2167.

[14] K. Koźmińsk and E. Kinnen, An algorithm for finding a rectangular dual of a planar graph for use in area planning for vlsi integrated circuits, 21st Design Automation Conference Proceedings, IEEE, 1984, pp. 655–656.

[15] K. Koźmińsk and E. Kinnen, Rectangular duals of planar graphs, Networks 15 (1985), no. 2, 145–157.

[16] K. Koźmińsk and E. Kinnen, Rectangular dualization and rectangular dissections, IEEE Transactions on Circuits and Systems 35 (1988), no. 11, 1401–1416.

[17] M. Kurowski, Simple and efficient floor-planning, Inform. Process. Lett. 86 (2003), no. 3, 113–119.

[18] Y.-T. Lai and S.M. Leinwand, A theory of rectangular dual graphs, Algorithmica 5 (1990), no. 1-4, 467–483.

[19] P.H. Levin, Use of graphs to decide the optimum layout of buildings, The Architects’ Journal 7 (1964), 809–815.

[20] C.-C. Liao, H.-I. Lu, and H.-C. Yen, Compact floor-planning via orderly spanning trees, J. Algorithms 48 (2003), no. 2, 441–451.

[21] S.-I. Nakano and M. Yoshikawa, A linear-time algorithm for bend-optimal orthogonal drawings of biconnected cubic plane graphs, International Symposium on Graph Drawing, Springer, 2000, pp. 296–307.

[22] T. Nishizeki and M.S. Rahman, Planar graph drawing, vol. 12, World Scientific Publishing Company, 2004.

[23] A. Papakostas and I.G. Tollis, Improved algorithms and bounds for orthogonal drawings, International Symposium on Graph Drawing, Springer, 1994, pp. 40–51.

[24] M.S. Rahman, S.-I. Nakano, and T Nishizeki, Box-rectangular drawings of plane graphs, J. Algorithms 37 (2000), no. 2, 363–398.

[25] M.S. Rahman, S.-I. Nakano, and T. Nishizeki, A linear algorithm for bend-optimal orthogonal drawings of triconnected cubic plane graphs, Graph Algorithms And Applications I, World Scientific, 2002, pp. 343–374.

[26] M.S. Rahman, S.-I. Nakano, and T. Nishizeki, Rectangular drawings of plane graphs without designated corners, Com-
put. Geom. 21 (2002), no. 3, 121–138.

[27] M.S. Rahman and T. Nishizeki, Bend-minimum orthogonal drawings of plane 3-graphs, International Workshop on Graph-Theoretic Concepts in Computer Science, Springer, 2002, pp. 367–378.

[28] M.S. Rahman, T. Nishizeki, and S.-I. Nakano, Rectangular grid drawings of plane graphs, Computational Geometry 10 (1998), no. 3, 203–220.

[29] M.S. Rahman, T. Nishizeki, and M. Naznin, Orthogonal drawings of plane graphs without bends, Graph Algorithms And Applications 4, World Scientific, 2006, pp. 335–362.

[30] I. Rinsma, Existence theorems for floorplans, Bull. Austral. Math. Soc. 37 (1988), no. 3, 473–475.
[31] I. Rinsma, Rectangular and orthogonal floorplans with required room areas and tree adjacency, Environment and Planning B: Planning and Design 15 (1988), no. 1, 111–118.

[32] I. Rinsma, J.W. Giffin, and D.F. Robinson, Orthogonal floorplans from maximal planar graphs, Environment and Planning B: Planning and Design 17 (1990), no. 1, 57–71.

[33] K. Shekhawat, J.P. Duarte, and Pinki, A graph theoretical approach for creating building floor plans, International Conference on Computer-Aided Architectural Design Futures, Springer, 2019, pp. 3–14.

[34] K. Shekhawat and P. Pinki, Construction of architectural floor plans for given adjacency requirements, RE: Anthropocene, Design in the Age of Humans - Proceedings of the 25th CAADRIA Conference, Cumincad, 2020, pp. 315–323.

[35] Y. Sun and M. Sarrafzadeh, Floorplanning by graph dualization: L-shaped modules, Algorithmica 10 (1993), no. 6, 429–456.