Introduction
The floorplanning automation has been well studied in the literature where different approaches, such as artificial intelligence, graph theory, shape grammar, and optimization, have been widely used. In this paper, we present a graph-theoretic approach for the automated generation of multiple floorplans.
A floorplan is a polygon, which is the plan boundary, divided by straight lines into component polygons called rooms. Corresponding to a floorplan, there associates a graph called dual graph, which is obtained by replacing each room by a vertex and any two vertices are adjacent, that is, joined by an edge, if the corresponding rooms share a wall or a section of a wall. For example, in Figure 1, the dual graph (Fig. 1b) of a floorplan (Fig. 1a) is shown. Constructing the dual graph of a floorplan is easy but deriving a floorplan from the dual graph (in this case, we call the dual graph as an adjacency graph) is not obvious. For example, Figure 1c represents an adjacency graph for which constructing a floorplan manually is a difficult task. Also, it is interesting to observe that the adjacency graph represents the geometrical and topological constraints of a floorplan. For example, the shape of the room is not provided explicitly by the user but from the graph in Figure 1b; it can be observed that at least one of the rooms needs to be non-rectangular (room 1 is non-rectangular in Fig. 1a) because of the presence of separating triangle 
$\triangle 135$ (refer to Definition 4). Further, the position of a vertex (in the given embedding of a graph) as internal or external vertex guides the position of the corresponding room. In Figure 1a, room 5 is internal while room 2 is external as suggested by the given graph.
Fig. 1. Adjacency and connectivity graph and corresponding floorplans.
Two rooms are adjacent if they share a wall among themselves where sharing a wall may not imply that the corresponding rooms are connected, mainly via a door. The connectivity of rooms is given by the connectivity graph which must be a sub-graph of the adjacency graph. For example, Figure 1e,f represents adjacency and connectivity graphs, respectively, and the corresponding floorplan is shown in Figure 1g. In this paper, we present graph-theoretic algorithms for generating a set of floorplans corresponding to a given adjacency graph and connectivity graph while satisfying dimensional constraints given in the form of width, height, and aspect ratio of each room. Further, we give an algorithm for inserting circulation in the obtained floorplan.
Literature review
The generation of floorplans using graph-theoretic tools has been well studied in the literature. It started in the 1960s (Levin, Reference Levin1964) and then in the subsequent years, a lot of research has been done which is focused on enumeration and construction of floorplans corresponding to a given graph (Steadman, Reference Steadman1973; Mitchell et al., Reference Mitchell, Steadman and Liggett1976). Koźmiński and Kinnen (Reference Koźmiński and Kinnen1985) gave a necessary and sufficient condition for the existence of rectangular floorplans (RFPs) corresponding to 1-connected and 2-connected planar triangulated graphs (PTGs). Bhasker and Sahni (Reference Bhasker and Sahni1988) gave a linear time algorithm for the construction of a RFP corresponding to 2-connected PTGs. At the same time, Rinsma (Reference Rinsma1987) discussed the existence of RFPs for given adjacencies and dimensions.
Yeap and Sarrafzadeh (Reference Yeap and Sarrafzadeh1993) realized that there are graphs for which RFPs do not exist. Liao et al. (Reference Liao, Lu and Yen2003) gave a linear time algorithm for constructing orthogonal floorplans (OFPs) for maximal planar graphs. Marson and Musse (Reference Marson and Musse2010) generated sliceable floorplans having aspect ratios close to one, without considering the adjacency constraints. Eppstein et al. (Reference Eppstein, Mumford, Speckmann and Verbeek2012) gave a necessary and sufficient condition for an RFP to be area universal.Footnote 1 They also proposed the construction of area-universal RFPs. Alam et al. (Reference Alam, Biedl, Felsner, Kaufmann, Kobourov and Ueckerdt2013) gave the construction of area-universal OFPs for maximal planar graphs. Wang et al. (Reference Wang, Yang and Zhang2018) introduced prototype GADG (graph approach to floor plan generation) for regenerating an existing RFP by considering the underlying graph of the existing floorplan. In the same year, Shekhawat and Duarte (Reference Shekhawat and Duarte2018) introduced generic RFPs and Shekhawat (Reference Shekhawat2018) proposed an algorithm for their enumeration. Upasani et al. (Reference Upasani, Shekhawat and Sachdeva2020) developed a prototype which transforms a drawn rectangular arrangement into a dimensioned RFP while satisfying adjacency and symmetric requirements. In the same year, Wang and Zhang (Reference Wang and Zhang2020) extended GADG (Wang et al., Reference Wang, Yang and Zhang2018) for generating dimensioned floorplans corresponding to user-specified design requirements. Shi et al. (Reference Shi, Soman, Han and Whyte2020) used reinforcement learning-based heuristic search technique (Monte Carlo Tree Search) to produce a closest RFP corresponding to any given adjacency graph.
There also exist other methodologies for generating floorplans. Shape grammar is an efficient approach for automation where the idea is to generate designs through the execution of shape rules (Mitchel, Reference Mitchel1990; Duarte, Reference Duarte2005; Müller et al., Reference Müller, Zeng, Wonka and Van2007; Wu et al., Reference Wu, Yan, Dong, Zhang and Wonka2014). Evolutionary approaches are also well studied for this purpose (Rodrigues et al., Reference Rodrigues, Gaspar and Gomes2013). Wu et al. (Reference Wu, Fan, Liu and Wonka2018) presented a hierarchical framework and used mixed-integer quadratic programing for the dimensioning of layouts with fixed exterior boundaries. In recent times, many new approaches have evolved for supervised floorplan automation (Merrell et al., Reference Merrell, Schkufza and Koltun2010; Wu et al., Reference Wu, Fu, Tang, Wang, Qi and Liu2019). Hu et al. (Reference Hu, Huang, Tang, Matias, Kaick, Zhang and Huang2020) presented the generation of floorplans using a graph neural network while considering room adjacencies in the form of layout graphs. Laignel et al. (Reference Laignel, Pozin, Geffrier, Delevaux, Brun and Dolla2021) used a genetic optimization approach for the automated generation of apartment layouts where the area of rooms and boundary layout have been considered as input.
In this paper, we present a prototype based on graph-theoretic algorithms and optimization tools for generating multiple floorplans while satisfying given adjacency, boundary, and size constraints.
Fig. 2. Illustration for different terminologies.
Gaps in the existing literature and proposed work
The gaps in the existing literature can be listed as follows:
(i) Floorplans for 1-connected PTGs
It can be easily seen in the literature that graph-theoretic algorithms for generating floorplans are restricted to 2-connected PTGs (Bhasker and Sahni, Reference Bhasker and Sahni1988; Kant and He, Reference Kant and He1993; Yeap and Sarrafzadeh, Reference Yeap and Sarrafzadeh1993; Liao et al., Reference Liao, Lu and Yen2003; Alam et al., Reference Alam, Biedl, Felsner, Kaufmann, Kobourov and Ueckerdt2013; Shekhawat et al., Reference Shekhawat, Upasani, Bisht and Jain2021). In this paper, we propose a graph-theoretic algorithm for the construction of a floorplan corresponding to any given graph.
(ii) Dimensioned floorplans
In the 1980s, authors proposed the dimensioning of RFPs. Roth et al. (Reference Roth, Hashimshony and Wachman1982) suggested the use of PERT technique which often resulted in non-rectangular rooms. More recently, Wang and Zhang (Reference Wang and Zhang2020) generate dimensioned floorplans with fixed aspect ratio constraints; however, a generalized optimization technique for producing feasible floorplans for any given room dimensions is still not available. In this paper, we consider minimum and maximum width, as well as area for each room as dimensional constraints, and using graph-theoretic and optimization tools, we construct a floorplan satisfying the given constraints.
(iii) Boundary constraints
Recently, Wang and Zhang (Reference Wang and Zhang2020) considered boundary constraints for the generation of floorplans. In this paper, we propose a graph-based algorithm for generating multiple floorplans satisfying boundary constraints where users can choose the preferred location for each room based on cardinal and inter-cardinal directions.
(iv) Circulations
Baybars (Reference Baybars1982) presented a graph-theoretical approach for inserting circulations within a floorplan. Recently, Egor et al. (Reference Egor, Sven, Martin and Reinhard2020) gave an evolutionary algorithm for inserting circulations. In this paper, we present an algorithm for generating floorplans along with spanning circulations.
(v) Time complexity
Many existing works can produce residential building layouts for a small number of rooms (Merrell et al., Reference Merrell, Schkufza and Koltun2010; Wu et al., Reference Wu, Fan, Liu and Wonka2018; Nisztuk and Myszkowski, Reference Nisztuk and Myszkowski2019), but for the complex building structures with a large number of rooms, we need efficient algorithms. The proposed prototype takes
$O( N^{2})$ space for generating floorplans for any given number of rooms $N$.
Preliminaries
In this section, we present a few important terminologies which are used frequently in literature and also throughout this paper.
Definition 1 (Floorplans)
Floorplans can be categorized on the basis of the shape of rooms and the boundary of a layout. If the boundary and all the rooms of a plan are rectangular, we call it rectangular floorplan, denoted as RFP. If the boundary is rectangular and at least one of the rooms is orthogonal, we call it orthogonal floorplan, denoted as OFP. Floorplans other than RFPs and OFPs are termed as non-rectangular floorplans (NRFPs). For example, the floorplan in Figure 1a is an OFP, in Figure 1d is an RFP, and in Figure 10e is an NRFP. Unless specified, a floorplan refers to a dimensionless floorplan. In the literature, floorplans are generally without empty spaces but we show that for non-triangulated graphs, floorplans have empty spaces (Fig. 11b).
Two rooms in a floor plan are adjacent if they share a wall or a section of it, where a wall of a room refers to the edges forming its perimeter.
Definition 2 (Graphs)
A graph 
$G$ is a finite nonempty set 
$V( G)$ of vertices and a (possibly empty) set 
$E( G)$ of 2-element subsets of 
$V( G)$ called edges. 
$G$ is said to be planar if it can be embedded in the plane without crossing of edges; otherwise, it is a non-planar graph (the graph in Fig. 2a is non-planar while the graph in Fig. 2b is planar whose planar embedding is shown in Fig. 2c). A plane graph is a planar graph with an embedding dividing the plane into connected components called faces/regions (the graph in Fig. 2c has five internal faces and one exterior face).
A floorplan itself is a planar-connected graph where each room is the face of the floorplan. Therefore, we are considering planar-connected graphs only and in the paper, a graph shall mean a connected planar graph. In architectural terms, when the given graph provides a specific neighborhood of each room, we call it an adjacency graph, denoted as 
$G_A$. A connectivity graph, denoted as 
$G_C$, is a sub-graph of the adjacency graph representing the connectivity of rooms (via a door). Figure 1e,f represents adjacency and connectivity graphs, respectively.
Definition 3 (Graph connectivity)
A graph 
$G$ is said to be connected if there is a path from each vertex to any other vertex. It is obvious that the adjacency graph is always planar and connected. A connected graph 
$G$ is said to be 1-connected if it has a cut-vertex. A vertex 
$v$ is said to be a cut-vertex if its removal disconnects the graph. 
$G$ is said to be bi-connected or 2-connected if it has no cut-vertices. The graph in Figure 2d is 1-connected having vertex 2 as a cut-vertex while the graph in Figure 2e is 2-connected with no cut-vertices.
Definition 4 (Triangulation)
A connected planar graph is triangulated if all of its faces (except the exterior) are triangular; the exterior face may or may not be a triangle. This graph is known as inner PTG (the graphs in Figure 2d–f are PTGs).
A separating triangle 
$\triangle abc$ is a cycle of length three in a graph 
$G$ such that 
$G-\triangle abc$ is a disconnected graph. It is denoted as ST. 
$\triangle 234$ in Figure 2e is a separating triangle.
A PTG with no separating triangle and with the exterior face of the length at least 4 is called properly triangular planar graph (PTPG) (Bhasker and Sahni, Reference Bhasker and Sahni1987). The graph shown in Figure 2f is a PTPG, whereas the graphs shown in Figure 2d,e are not PTPGs because of the presence of STs.
Definition 5 (Corner implying path (CIP) (Bhasker and Sahni, Reference Bhasker and Sahni1987))
A shortcut in a planar bi-connected graph 
$G$ is an edge that is incident to two vertices on the outer boundary of 
$G$ but is not a part of the outer boundary. The edge 
$( 2,\; 4)$ in Figure 2f is a shortcut. A CIP in a planar bi-connected graph 
$G$ is a path 
$u_1,\; u_2,\; \ldots ,\; u_n$ on the outer boundary of 
$G$ with the property that 
$( u_1,\; u_n)$ is a shortcut and 
$u_2,\; u_3,\; \ldots ,\; u_{n-1}$ are not the endpoints of any shortcut. 2–3–4 in Figure 2f is a CIP.
Definition 6 (Regular edge labeling (REL) (Kant and He, Reference Kant and He1993))
An REL of a bi-connected PTPG 
$G$ is a partition of the interior edges of 
$G$ into two subsets 
$T_1$, 
$T_2$ of directed edges such that for each interior vertex 
$u$, the edges incident to 
$u$ appear in a counterclockwise order around 
$u$ as follows: a set of edges in 
$T_1$ leaving 
$u$, a set of edges in 
$T_2$ entering 
$u$, a set of edges in 
$T_1$ entering 
$u$, and a set of edges in 
$T_2$ leaving 
$u$.
Let 
$N,\; E,\; S,\; W$ be the four exterior vertices in clockwise order. All interior edges incident to 
$N$ are in 
$T_1$ and entering 
$N$. All interior edges incident to 
$E$ are in 
$T_2$ and entering 
$E$. All interior edges incident to 
$S$ are in 
$T_1$ and leaving 
$S$. All interior edges incident to 
$W$ are in 
$T_2$ and leaving 
$W$. An REL for the PTPG in Figure 4a is shown in Figure 4c.
Methodology
In this section, we present the construction of floorplans with circulations for any given adjacency and connectivity graphs while satisfying boundary and dimensional constraints.
Floorplans for 1-connected and non-triangulated graphs
In the literature, the construction of floorplans is restricted to 2-connected PTGs only. Koźmiński and Kinnen (Reference Koźmiński and Kinnen1985) proved that there exists an RFP for a 2-connected PTPG if and only if it has at most four CIPs. Recently, Shekhawat et al. (Reference Shekhawat, Upasani, Bisht and Jain2021) presented a prototype GPLAN which is capable of generating RFPs for any 2-connected PTPG with at most four CIPs and it generates OFPs for 2-connected PTGs having separating triangles or more than four CIPs (refer to Fig. 3). The steps of the algorithm for constructing a floorplan corresponding to a given PTPG are illustrated in Figure 4, which are briefly explained as follows:
(i) 4-completion: This step identifies rooms, which form the boundary of a floorplan based on cardinal directions north, west, south, and east. Kant and He (Reference Kant and He1993) proposes the addition of four new vertices
$n,\; w,\; s,\; e$ representing north, west, south, and east, respectively, to a given bi-connected PTPG. This process requires 4 corner vertices on the outer boundary which are obtained by using the concept of CIPs (see Definition 5).
Fig. 3. Floorplans corresponding to bi-connected PTGs.
Fig. 4. Constructing a floorplan corresponding to a given bi-connected PTPG.
For the graph in Figure 4a, 4-completion is illustrated in Figure 4b where rooms 6 and 7 form north boundary and other exterior rooms form remaining boundaries.
(ii) REL: Constructing an REL of a given graph helps us in identifying horizontal and vertical adjacencies within a floorplan. Kant and He (Reference Kant and He1993) proposed an algorithm for transforming a bi-connected PTPG obtained by 4-completion into a REL. This algorithm first removes all the vertices in a described order and then adds the label
$T_1$ and $T_2$ to the edges while adding the vertices. For a better understanding, refer to Figures 5–7 where a good vertex in a PTPG is an inner vertex with the following properties:
(a) has degree 4 and (has at most 1 heavy neighbor or has 2 non-adjacent heavy neighbors)
(b) has degree 5 and has at most 1 heavy neighbor
Fig. 5. Edge contractions.
Fig. 6. Trivial regular edge labeling.
Fig. 7. Edge expansions.
The contractible neighbor (of a good vertex) is defined as follows:
Let
$u$ be a neighboring vertex of a good vertex $v$, and $y$ and $z$ be their two common neighbors. If $x$ ($\neq y,\; z$) is any other neighbor of $v$, then only mutual neighbor(s) of $u$ and $x$ must be $v$ (or either of $y$ or $z$) for $u$ to be a contractible neighbor of $v$.Based on the REL in Figure 4c, the horizontal and vertical adjacencies are shown in Figure 4d,e, respectively.
(iii) Floorplan: Using the horizontal and vertical adjacencies, next is to construct two separate floorplans satisfying these adjacencies as shown in Figure 4f,g, respectively, and then merging these floorplans gives us the required floorplan as given in Figure 4h. The merging of horizontal and vertical floorplans are illustrated in Figure 8.
Fig. 8. The steps of construction of an RFP from the obtained REL.
In case of a non-triangulated (bi-connected) graph 
$G$, we first triangulate 
$G$ by adding new edges to have a triangulated bi-connected graph 
$G'$ (refer to Fig. 9a,b). For triangulation, the algorithm given by Berry et al. (Reference Berry, Blair, Heggernes and Peyton2004) has been used. Each of the added edges is subdivided by introducing new vertices as shown in Figure 9c. The obtained graph is further triangulated to have a bi-connected triangulated graph (Fig. 9d) for which a floorplan is constructed (Fig. 9e). In the obtained floorplan, rooms corresponding to added vertices are removed to have a floorplan corresponding to the input graph as shown in Figure 9f. It is interesting to note here that any cycle 
$C$ of length greater than 3 represents an empty space (can be seen as an atrium) in the corresponding floorplan surrounded by the rooms corresponding to the cycle 
$C$. For example, refer to the graph in Figure 9a having two cycles of length greater than 3 and corresponding floorplan is shown in Figure 9f having two atria.
Fig. 9. Floorplan corresponding to a non-triangulated bi-connected PTG.
In case of a 1-connected PTG 
$G$, we first biconnect it by adding new edges (refer to Fig. 10a,b). Then new vertices are introduced for sub-dividing the new added edges, which are followed by triangulation (see Fig. 10c). For the obtained graph, a floorplan is constructed from which rooms corresponding to added vertices are removed to have a required floorplan as shown in Figure 10d,e, respectively. 1-connected graphs are very useful in representing different blocks of a building connected through cut-vertices. For example, in Figure 11a, two blocks made up of rooms 
${ R_1,\; R_2,\; R_3,\; R_4 }$ and 
${ R_5,\; R_6,\; R_7,\; R_8 }$ are connected through room 
$R_0$.
Fig. 10. Floorplan corresponding to a 1-connected PTG.
Fig. 11. Floorplans corresponding to adjacency graph and connectivity graph.
When the adjacency graph is 1-connected and non-triangulated, we first biconnect it and then triangulate it by adding new edges. Using the proposed methodology, GPLAN is capable of generating floorplans for any given adjacency graphs (refer to Fig. 11b where using GPLAN, we obtained a floorplan corresponding to a 1-connected non-triangulated adjacency graph shown in Fig. 11a).
Connectivity graph
The information given by an adjacency graph explains a floorplan in terms of how rooms share a wall (full or partial) with each other. It represents the architectural program in terms of the set of rooms composing the plan and their relative position in terms of which spaces share walls with others. This is more informative of compositional concepts rather than the spatial relations between rooms (connections between rooms, which could be represented with a connectivity graph). In GPLAN, the user can give adjacency graph and connectivity graph simultaneously. For example, Figure 11c represents an adjacency graph (the complete graph with red and black edges) and a connectivity graph (graph induced by red edges) and Figure 11d represents the required floorplan where doors are corresponding to the edges of the connectivity graph.
Multiple floorplans
For a given adjacency graph, we aim to construct all possible floorplans. This can be done in two ways as follows:
(i) by considering each room adjacency in two ways as horizontal and vertical adjacency.
For example, refer to Figure 12 where floorplans corresponding to a given graph are topologically distinct because there exists at least a pair of rooms in these floorplans having different adjacency orientation (horizontal and vertical), that is, rooms 3 and 12 are horizontally adjacent in Figure 12b but they are vertically adjacent in Figure 12c. By looking at all possible combinations, GPLAN generates all topologically distinct floorplans. Eppstein et al. (Reference Eppstein, Mumford, Speckmann and Verbeek2012) propose the concept of flippable edges and vertices to define a partial ordering on the family of all regular edge labeling of a given graph. A flippable edge is an edge
$e$ which is not adjacent to a degree-4 vertex, and the 4-cycle surrounding $e$ is alternately labeled in the REL (edge (6, 9) is flippable in the REL in Fig. 13a). A flippable vertex $v$ is a four-degree vertex such that the four-cycle surrounding $v$ is alternately labeled in the REL (Fig. 13a has no flippable vertex). A new REL can always be obtained using a flippable edge or a flippable vertex (Eppstein et al., Reference Eppstein, Mumford, Speckmann and Verbeek2012) (the REL in Fig. 13b is obtained from the REL in Fig. 13a by flipping the edge (6, 9) and corresponding floorplans are illustrated in Fig. 13c,d, respectively).(ii) by considering different boundary constraints.
Fig. 12. Different floorplans corresponding to a given graph.
Fig. 13. Flippable edge and REL.
The vertices which lie on the exterior face of a graph (with a fixed embedding) correspond to the exterior rooms in a floorplan. Thus, the exterior vertices and corresponding rooms can be adjacent to the exterior through north, east, west, or south side. For example, rooms 3 and 12 are adjacent to the north in Figure 12b while in Figure 12c, rooms 4, 11, and 7 are adjacent to the north. Thus, GPLAN iterates through all possible boundaries to enumerate floorplans with different boundaries.
To generate all possible floorplans, we consider all possible boundary conditions and all combinations of horizontal and vertical room adjacencies. For example, for the graph in Figure 12a, GPLAN produces 6928 floorplans while considering 424 different boundaries as shown in Figure 12d. Similarly, for the graph in Figure 14, GPLAN constructs 101 different floorplans, a few of them are illustrated in Figure 15.
Fig. 14. Computing the number of different floorplans corresponding to a given graph.
Fig. 15. Multiple floorplans.
Time complexity
For a single floorplan generation, GPLAN first transforms the graph into a bi-connected triangulated graph (Berry et al., Reference Berry, Blair, Heggernes and Peyton2004) which is an 
$O( N^{2})$ algorithm where 
$N$ refers to the number of rooms in the floorplan. GPLAN then performs 4-completion of the transformed graph, which takes linear time. The single floorplan is then generated using REL and merging horizontal and vertical floorplans using the algorithm proposed in Kant and He (Reference Kant and He1993). This algorithm runs in 
$O( N)$ time using an adjacency list as the data structure for the input graph. Combining these steps, GPLAN generates a floorplan in 
$O( N^{2})$ time.
For multiple floorplans, GPLAN generates a family of all possible RELs for the graph. The algorithm proposed for the same by Eppstein et al. (Reference Eppstein, Mumford, Speckmann and Verbeek2012) runs in polynomial time. These RELs are then transformed into floorplans by merging them using 
$O( N)$ algorithm proposed in Kant and He (Reference Kant and He1993). Combining these steps, GPLAN generates all possible topologically distinct floorplans in polynomial time.
GPLAN uses an adjacency list to store the input graph, which takes 
$O( N + M)$ space where 
$M$ is the number of adjacencies in the floorplan. The output floorplan is stored in a list of tuples where each tuple contains the coordinates of the corner of each room. Eppstein et al. (Reference Eppstein, Mumford, Speckmann and Verbeek2012) prove that the number of different RELs for a given graph is 
$O( N)$. For a single floorplan, the space complexity of GPLAN is 
$O( N + M)$. For multiple floorplans, GPLAN takes 
$O( N^{2})$ space.
Dimensioned and symmetric floorplans
In Shekhawat et al. (Reference Shekhawat, Upasani, Bisht and Jain2021), authors have presented a linear optimization model for producing dimensioned layouts corresponding to a given bi-connected PTG where dimensions are given in the form of minimum and maximum width, as well as the height of each room. In this paper, we have modified this model for 1-connected non-triangulated planar graphs. Further, in the previous model, the aspect ratio constraints for each room were not considered which may have led to very thin rooms which are not architectural acceptable. Hence, we have introduced aspect ratio constraints for each room. Refer to Figure 16, where for the given graph and dimensional constraints, a dimensioned floorplan is shown. Similarly, a dimensioned floorplan for the 1-connected graph in Figure 16d is shown in Figure 16e. Also, if the dimensional constraints are not feasible, GPLAN generates an error as shown in Figure 17d where dimensional constraints in Figure 17c are not feasible. The linear optimization model corresponding to horizontal and vertical st-graphs is given as follows:
$$\matrix{\text{Minimize : } \quad & \displaystyle\sum w( e_{\,j, i}) - d_{i}^{{\rm max}} \cr \text{such that : } \quad & \displaystyle\sum w( e_{\,ji}) = \displaystyle\sum w( e_{ik}) \quad \forall i \in V( G) \cr & \min( d_i) \leq \displaystyle\sum w( e_{\,ji}) \leq \max( d_i) \quad \forall i \in V( G) },$$where 
$d_{i}^{{\rm max}}$ is the maximum dimension (width/height) of room 
$i$, 
$\sum w( e_{ji})$ denotes the total inflow, and 
$\sum w( e_{ik})$ denotes the total outflow from vertex 
$i$.
Fig. 16. Dimensioned floorplans for given graphs.
Fig. 17. A symmetric floorplan for a given graph.
Taking these constraints into account, GPLAN optimizes width and height separately using the dual-simplex method to generate a feasible dimensioned floorplan. For a better understanding, refer to Tables 1–4 giving constraints corresponding to the st-graphs in Figure 16d,e and dimensional constraints in Figure 16b.
Table 1. Constraints corresponding to vertical st-graph in Figure 4e and dimensional constraints in Figure 16b
Table 2. Constraints corresponding to horizontal st-graph in Figure 4d and dimensional constraints in Figure 16b
Table 3. Aspect ratio constraints corresponding to dimensional constraints in Figure 16b
Table 4. Modified height constraints due to aspect ratio constraints corresponding to dimensional constraints in Figure 16b
In addition to it, we introduce rooms symmetry using the linear optimization model where either we can make two rooms symmetric to each other or we can make the combination of two adjacent rooms symmetric to a third room. Refer to the floorplan in Figure 16c where rooms 0 and 2 have the same dimensions as asked by the user. The concept of rooms symmetry can be very helpful in generating symmetric floorplans corresponding to symmetric graphs. The graph in Figure 17a is symmetric and if we ask rooms (0, 1), (2, 3), and (4, 5) to be symmetric, GPLAN produces a floorplan symmetric about 
$x$-axis and 
$y$-axis as shown in Figure 17b. In future, we try to develop an algorithm to identify symmetric graphs and to generate symmetric floorplans automatically.
Fig. 19. Inserting circulation within a floorplan.
Floorplans with boundary constraints
It has already been seen that GPLAN is capable of producing a lot of distinct layouts which are not easy to handle. To refine the set of all possible layouts, in this section, we impose boundary and dimensional constraints on these layouts. For the boundary constraints, users will be asked to choose the preferred location of each room based on cardinal and inter-cardinal directions. Also, among all possible layouts, we need to look for those layouts which satisfies dimensional restrictions. For example, for the graph in Figure 16a, GPLAN can produce 101 layouts but for the given boundary and dimensional constraints in Figure 18, there exist only 40 floorplans, a few of them are shown in Figure 18.
Fig. 18. Dimensioned floorplans with boundary constraints.
Spanning circulations
A circulation refers to the way people move through and interact within a building. A spanning circulation space stands for a single interior courtyard adjacent to each of the rooms of a floorplan.
In this section, we first present an algorithm for enumerating spanning circulation inside a floorplan assuming that floorplans have only one entrance.
Let 
$f$ be the number of interior faces in 
$G( V,\; E)$ (dual of the floorplan), represented as 
$F_1,\; F_2,\; \ldots ,\; F_f$. Also, consider 
$E = { e_1,\; e_2,\; \ldots ,\; e_m}$ and 
$V = { v_1,\; v_2,\; \ldots ,\; v_n}$ are the edge set and vertex set of 
$G$, respectively. The steps of the algorithm for generating circulations are as follows (for understanding the steps of the algorithm, refer to Figure 19a,b, where a floorplan and corresponding dual graph are illustrated):
1. Choose a face, say
$F_1$, of $G$ having an exterior edge, say $e_1$ (edges adjacent to the exterior are called exterior edges).For example, corresponding to Figure 19b, we choose face
$F_1$ consisting of vertices $v_1,\; v_2,\; v_7$.2. Consider an empty set
$S$. Add all three vertices that form $F_1$ to $S$. For example, corresponding to Figure 19c, $S = { v_1,\; v_2,\; v_7 }$.3. Insert a new vertex, say
$V_{n + 1}$, on the exterior edge $e_1$. By inserting a new edge say $E_k$, make $V_{n + 1}$ adjacent to a vertex of $F_1$ that is not an end-point of $e_1$. For example, $V_8$ and $E_{15}$ are shown in Figure 19c (in Fig. 19, inserted vertices are marked by red color while inserted edges are illustrated by dotted lines).4. Insert a rectangular circulation space, say
$C_{n + 1}$, corresponding to $V_{n + 1}$ in the corresponding floorplan. For example, in Figure 19d, inserted circulation space $C_8$ is adjacent to rooms $R_1$, $R_2$, and $R_7$. The conditions for inserting a circulation space are given in Step 9 (the inserted circulation spaces are demonstrated by gray color).5. Choose a face, say
$F_i$, $2\le i \le f$, to which an edge has not been inserted such that $F_i$ is adjacent to at least one of the faces to which an edge has already been inserted. Let $F_i$ be adjacent to $F_j$, $1\le j \le f$. For example, in Figure 19e, we choose a face consisting of vertices $v_2,\; v_7,\; v_3$ and is adjacent to $F_1$.6. Pick an edge
$e_j$ that belongs to both $F_i$ and $F_j$. Insert a new vertex, say $V_{k}$, $k\ge n + 2$, on $e_j$ and make $V_{k}$ adjacent to a vertex of $F_i$ that is not an end-point of $e_j$. For example, in Figure 19e, $V_9$ and $E_{16}$ have been inserted.7. Add all three vertices that form
$F_i$ to $S$. Corresponding to Figure 8e, $S = { v_1,\; v_2,\; v_7,\; v_3 }$.8. Insert a circulation space, say
$C_{k}$, corresponding to $V_{k}$ in the corresponding floorplan such that it preserves the adjacency relations of $V_{k}$, that is, it only satisfies the following adjacency requirements:
(a)
$C_{k}$ is adjacent to rooms corresponding to the vertices that are adjacent to $V_{k}$ (in Fig. 19f, $C_9$ is adjacent to $R_2$, $R_3$, and $R_7$),(b)
$C_{k}$ must be adjacent to one of the existing circulation space (in Fig. 19f, $C_9$ is adjacent to $C_8$),(c) Let the endpoints of
$e_j$ be $v^{1}_j$ and $v^{2}_j$. $C_{k}$ is inserted in such a way that it makes the rooms corresponding to $v^{1}_j$ and $v^{2}_j$ non-adjacent (in Fig. 19f, after inserting $C_9$, rooms $R_2$ and $R_7$ are non-adjacent),(d) to satisfy adjacency requirements,
$C_{k}$ can be inserted horizontally or vertically. For example, in Figure 19f, $C_9$ has been inserted vertically.
9. If
$S\subset V$, go to Step 6 otherwise stop. For example, corresponding to Figure 19b, a floorplan with all inserted circulation spaces is shown in Figure 19h.10. Adjoin all inserted circulation spaces to form a spanning circulation. For example, a floorplan with spanning circulation is shown in Figure 19i. Similarly, floorplans with different positions of spanning circulations are illustrated in Figure 19j,k.
Floorplans with circulation produced by GPLAN are shown in Figure 20, where by default the entrance is between rooms 0 and 1 (Fig. 20b), but a user has a choice to change the entrance (Fig. 20c) to have a new circulation (Fig. 20d). Once we have a spanning circulation, in the future, we would like to provide an option to the user to add and remove parts of circulations (in Fig. 19h, among circulation 8, 9, 10, 11, and 17, the user would be able to delete any of them).
Fig. 20. A floorplan with spanning circulations.
Conclusion and future work
In this work, we have proposed a graph-theoretic approach with a solid mathematical foundation which can handle many constraints simultaneously and able to generate a large amount of layouts for given adjacencies and dimensions. Also, along with adjacencies and dimensions, we have considered boundary and symmetric constraints, which help us to customize floorplans based on users requirements. At this stage, this work, in general, proposes floorplan construction, which has applications in housing design (Hu et al., Reference Hu, Huang, Tang, Matias, Kaick, Zhang and Huang2020), game layout design (Ma et al., Reference Ma, Vining, Lefebvre and Sheffer2014), VLSI design (Kahng et al., Reference Kahng, Lienig, Markov and Hu2011), etc. In future, we aim to customize this work for housing design where the user only needs to present his requirements in terms of spaces and GPLAN would automatically provide a set of layouts. Also, to automate the process, one of the approaches is to derive data, mainly adjacency and dimensions, from the existing floorplans and use these data to produce multiple layouts (Wu et al., Reference Wu, Fu, Tang, Wang, Qi and Liu2019), which we aim to do in future. It can also be noticed that a very small amount of work has been done where boundary layout has been considered as input (Laignel et al., Reference Laignel, Pozin, Geffrier, Delevaux, Brun and Dolla2021). In future, we aim to develop graph-based algorithms for generating floorplans with given boundary layouts.
We agree that architects can never be replaced by a software, at the same time, it may not be feasible for them to propose multiple drawings to the user. Here, we aim to assist architects by providing them the initial layouts. Also, in developing countries, architects are out of reach to a large amount of population and therefore most of the houses are built without getting any assistance from the architects. Hence, there is a need for such a software that can generate layouts for the users which are architecturally feasible (if not optimal and stylish). In future, we would try to customize GPLAN so that it can address the need for housing designs for the required population.
Supplementary material
The supplementary material for this article can be found at https://doi.org/10.1017/S0890060421000275
Conflict of interest
The authors report no conflicts of interest.
Krishnendra Shekhawat is presently working as an Associate Professor at Department of Mathematics, BITS Pilani, India. He joined BITS Pilani as an Assistant Professor in 2016. Prior to this joining, he worked as a post-doctoral fellow in the guidance of Prof. Jose P. Duarte at University of Lisbon. He has completed his PhD in Mathematics from University of Geneva in the guidance of Prof. Daniel Coray. He is working in the field of Geometric Graph Theory and Architectural Design.
Rahil N. Jain is about to complete an Integrated degree of M.Sc. (Hons.) Mathematics and B.E. (Hons.) Computer Science from BITS Pilani, India. He has a publication in the journal Automation in Construction. He has a keen interest in Graph Theory and Machine Learning.
Sumit Bisht is a senior at BITS Pilani, India where he is majoring in Mathematics and Computer Science. He has been working on solving architectural design problems using graph theory for the last 3 years under the guidance of Prof. Krishnendra Shekhawat and has co-authored a paper in the same. His research interests lie in Computational Graph Theory and Deep Learning.
Aishwarya Kondaveeti is currently pursuing a dual degree program in M.Sc. Mathematics and B.E Computer Science at BITS Pilani, India. Her research interests lie in Computational Graph Theory and Optimization.
Dipam Goswami is a final year undergraduate student currently pursuing a dual degree, a BE in Computer Science, and an MSc in Mathematics from BITS Pilani, India. His research interests include Graph-theoretic Algorithms, Artificial Intelligence, Machine Learning, and Computer Vision. He has worked on developing graph-theoretic algorithms for generating rectangular floor plans.
