Keywords: graphs, mapping into rectangles, architectural design, floor plan.

The use of graph theory in architectural design has been shown by different authors [1,2,3]. Graphs can be used to represent in an abstract way different relationships (geometrical, functional, etc.) among the different floor rooms. This abstraction allows for the mathematical representation of the relationships that enable the automatic design processes [4].

A graph is a set of nodes or vertices connected by edges. If in an architectural plan a vertex is assigned to each room and an edge connecting two vertices is assigned to every wall, separating the corresponding rooms, a graph is obtained. It is said that the mentioned room distribution is a realisation of the graph into the floor plan. Each room distribution is associated to a graph, but a graph can be associated to different distributions

The possibility that the graph that represents the different relationships among the rooms can be associated to a distribution into a plan is designed as realisability of the graph into the plan. The different solutions to this problem are the different alternatives that can be considered by the designer in the preliminary design process stages.

Usually, floor plan sides are parallel or perpendicular to each other and rooms are rectangular. It is of interest to have algorithms [5] to verify the realisability of a graph by means of rectangles covering the given plan and if it is realisable, then automatically generate all possible distributions.

The problem can be solved into steps. The first step is to reduce the actual floor plan to a rectangular one. The second one is to check the realisability of the graph into a rectangular plan by rectangular rooms.

No algorithm has been found that solves this problem in a conclusive way. The authors presented a heuristic method based on the accomplishment of necessary conditions but they have not been able to prove its sufficiency although not counter- example has been found. Other author solutions that used graph theory to solve the problem of generating floor plan distributions are not prepared to cover a previously fixed floor plan and they need to impose previous decisions concerning relative positions between rooms. The method proposed by the authors is more general because it does not impose a-priori conditions on the relative positions of rooms, but it is only valid for rectangular plans, the only convex plans that can be covered by rectangles.

The algorithm developed by authors is structured in the following steps:

a)

If the floor plan is not rectangular then it is reduced to a rectangular one, by adding fictitious rooms. These new rooms are incorporated to the graphs to be checked.

b)

Check the realisability of the resulting graph over a rectangular plan.

c)

Generate all the topologically correct solutions over the rectangular plan.

d)

Check each solution considering other conditions (size, dimensions, orientations, fixed positions, etc) that allow for either rejecting it or weighting it using numerical criteria.

e)

Draw the solutions encountered (marking up the fictitious rectangles), and show them to the designer together with the obtained weights, so that he can make a decision.

Theoretical description of stages a-c was already presented in [5]. In this work, main details of the implementation in C of phase b are presented. Both, the data structure and the functions used by the program are described. Examples are included to show the complete application to a realisable graph and a set of examples of no realisable graphs is also included.

1

J. Gross and J. Yellen, "Graph Theory and its Applications", CRC. Press, 1999.

2

J. Roth and R. Hashimshony, "Algorithms in graph theory and their use for solve problems in Architectural design" Computer Aided Design, vol 2, pp 373-381, 1988. doi:10.1016/0010-4485(88)90214-X

3

Recuero, M. Alvarez and O. Río, "Grafos en el proyecto arquitectónico. Partición de un rectángulo en rectángulos", R.I. Métodos numéricos para el cálculo y diseño en ingeniería, vol. 12, 2, 1996.

4

Schwarz, D.M. Berry, E. Shabib, "Representing and solving the automatic building design problem", Computer Aided Design, vol 26.9, pp 689-698, 1994. doi:10.1016/0010-4485(94)90019-1

5

Recuero, O. Río, M. Alvarez, "Heuristic method to check the realisability of a graph into a rectangular plan", Advances in Engineering Software, vol 31, 2000. doi:10.1016/S0965-9978(99)00023-X

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)