Linear-time construction of floor plans for plane triangulations

Document Type : Original paper

Authors

1 Bits Pilani, Rajasthan

2 Department of Mathematics, BITS Pilani, Pilani Campus, Rajasthan - 333031

Abstract

This paper focuses on a novel approach for producing a floor plan (FP), either a rectangular (RFP) or an orthogonal (OFP) based on the concept of orthogonal drawings, which satisfies the adjacency relations given by any bi-connected plane triangulation $G$.
     Previous algorithms for constructing a FP are primarily restricted to the cases given below:
     \begin{enumerate}[(i)]
         \item A bi-connected plane triangulation without separating triangles (STs) and with at most 4 corner implying paths (CIPs), known as properly triangulated planar graph (PTPG).
         \item A bi-connected plane triangulation with an exterior face of length 3 and no CIPs, known as maximal planar graph (MPG).
     \end{enumerate}
     The FP obtained in the above two cases is a RFP or an OFP respectively. In this paper, we present the construction of a FP (RFP if exists, else an OFP), for a bi-connected plane triangulation $G$ in linear-time.

Keywords

Main Subjects

References

[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.
 
Communications in Combinatorics and Optimization
Volume 8, Issue 4
December 2023
Pages 673-692

Files

Share

How to cite

Statistics