Graph vision: Digital architecture’s skeletons

Graph Vision is the title of a new book by Theodora Vardouli. ¹ It is a history of applications of graph theory to architecture by researchers and designers in the 1960s and ‘70s. The genesis of this journal was rooted in research using relational systems, particularly graphs, during those years. Much of the early research into urban morphology, shape and design methods was published in Environment and Planning B, as noted when the journal’s 50th anniversary was celebrated last year ² (Batty, 2024).

Graphs have been key to many of the models and systems published in the journal. As a reminder, graph theory is the branch of discrete mathematics that deals with structural relationships. Entities are represented by points and relations between entities by lines joining pairs of points. The graphs can be drawn as diagrams. The theory has its origins in the work of Leonhard Euler in the eighteenth century and his famous ‘problem of the Königsberg bridges’. There was sporadic interest among mathematicians in the nineteenth century, but the first textbook was only published in 1936, and systematic development of the field dates from the 1960s.

Graphs were used by architectural researchers to represent the plans of buildings, the entities being rooms and the relationships those of adjacency of rooms, or access between rooms via doors. Graphs were also used in flow diagrams and in aids to the design process. The word ‘vision’ in Vardouli’s title refers, I take it, both to visualisation – making topological and structural relationships visible in graphic form – as well as to what were often visionary ambitions for a ‘scientific architecture’.

The book is divided into three main parts: ‘Images’, ‘Tools’ and ‘Infrastructures’. ‘Images’ deals with representation, with the ways in which graphs can be employed to visualise and analyse the underlying topological structure of architectural plans. Vardouli reproduces a drawing of the plans of three houses by Frank Lloyd Wright, designed according to three very different geometrical disciplines – rectangular, circular and triangular (Figure 1). If graphs are drawn in which the points stand for rooms and the lines stand for relationships of accessibility, it emerges that these three plans share the same graph (with the minor exception of one extra room in the triangular plan). The topology is identical. One meets the same rooms in the same sequences as one moves through each house. The graph separates out configuration from dimension and shape.

Figure 1.

Three house plans by Frank Lloyd Wright, and a graph of the relationships of access between rooms, which is the same in all cases, with the exception of one extra bedroom in the plan with triangular geometry. From Lionel March and Philip Steadman, The Geometry of Environment, 1971 pp. 27, 28.

The chapters on ‘Tools’ cover – among other topics – methods for putting graphs to work to produce supposedly ‘optimal’ plans automatically. Graphs were also used to depict the structure of complete design problems, where many considerations interact, not just those of plan layout. ‘Infrastructure’ has two meanings for Vardouli. The word describes giant built structures made of columns and floorplates but otherwise empty, into which many room layouts can be fitted and flexibly rearranged. The term also refers to an idea which interested a number of researchers: that, for suitably defined classes of plan, and using graph-based methods, it would be possible to enumerate all mathematical possibilities exhaustively. The activity of ‘design’ would then become a matter of selection from catalogues rather than the production of single plans to order. In Vardouli’s phrase, ‘… not what is best, but what is possible’. Such methods might, for example, generate, in theory, all possible plans for apartments that could be fitted into the empty built infrastructures.

At this point, I should declare a major interest. My work, among others, is featured prominently under ‘Images’ and ‘Infrastructures’. Figure 1 comes from a book, The Geometry of Environment, that Lionel March and I published in 1971. ³ March was the Director of the Centre for Land Use and Built Form Studies (LUBFS) at Cambridge University, set up by the Professor of Architecture Sir Leslie Martin (March was also the founding editor of Environment and Planning B). Several LUBFS researchers were working at that time on graph-theoretic representation including March, myself and Philip Tabor. Vardouli describes the contents of The Geometry of Environment at some length, with most emphasis on the coverage of graph theory in the second half of the book. Our declared purpose was to introduce architects to topics in discrete mathematics, as opposed to the descriptive geometry and proportional theory which had previously been the mathematical subjects of the architectural curriculum.

Vardouli introduces the radical French architect Yona Friedman, whose Ville Spatiale scheme of 1959 proposed an elevated space frame structure in which urban uses could be accommodated. For this, he provided a graph-based user manual with which prospective occupants could generate their own plan layouts. The method was embodied in a computer program called the ‘Flatwriter’. Friedman was in touch with the American mathematician Frank Harary, known to some for the ubiquity of his papers as ‘Mr Graph Theory’, and with the British Constructionist artist Anthony Hill who used graph theory among other purposes for analysing the paintings of Piet Mondrian. Friedman reported his work in a book, Pour une Architecture Scientifique, whose title deliberately echoed Le Corbusier’s Towards a New Architecture. ⁴

The story is told under ‘Tools’ of the sustained effort at this time to generate architectural plans by computer. These were early days for architectural CAD, but some of the first computational aids to design were programs in which a schedule of rooms was specified, together with a set of desired spatial relationships between rooms, expressed as a graph, and the machine produced one feasible layout, usually with the help of some kind of optimisation technique to find the ‘best’ arrangement. The objective function of this optimisation was generally to minimise the total distance travelled by the occupants of the plan each day or week. Surveys were made of people’s movements in existing buildings of the same type to provide data for the optimisation, and the results presented diagrammatically as graphs or ‘string diagrams’. Many applications were to hospital design. Vardouli gives most space to the work of Whitehead and Eldars and their paper ‘An approach to the optimum layout of single-storey buildings’ of 1964. ⁵

The philosophy of Philip Tabor’s approach at LUBFS to the question of plan layout and pedestrian circulation was diametrically different. Highly sceptical of the computer methods for optimisation, he studied the potential of simple ‘built forms’ – straight blocks, courts and cruciforms – for the accommodation of different generic patterns of movement. This was characteristic of the general approach of LUBFS which was not concerned with systematic design methods but with the production of scientific knowledge of options in planning and architecture to support design: in Leslie Martin’s words, with ‘ranges of choice’.

Vardouli’s second large topic under ‘Tools’ is the work of Christopher Alexander, moving from his first book Notes on the Synthesis of Form of 1964 to his Pattern Language of 1977. ⁶ Alexander was a leading if often uncomfortable figure in the ‘design methods movement’ of the 1960s and ‘70s, whose work has been much debated. Vardouli’s focus is again on the uses of graph theory. In the Notes, Alexander’s method is to list ‘misfits’ between the forms of buildings and their ‘contexts’ or environments, and to draw graphs of instances where these ‘misfits’ interact. The process in theory gives structured analyses of design problems, from which formal solutions can be generated. George Stiny has aptly said that a better title for the book would have been Notes on the Analysis of Function.

Alexander renounced this early work for reasons that he did not make explicit, but which I suspect had to do with logical contradictions whose nature I have discussed elsewhere. ⁷ In any case his pattern languages, by complete contrast, were catalogues of pre-designed parts or elements of buildings, at a scale larger than that of the components of construction, which were to be chosen and combined by designers – whether lay people or professionals – according to hierarchically ordered sequences presented by Alexander and colleagues as networks.

Finally, in ‘Infrastructures’ Vardouli discusses research on the enumeration of possible plans consisting of small numbers of rooms, as, for example, the plans of small houses or apartments. Bill Mitchell, Robin Liggett and I worked on catalogues of plans consisting of rectangular rooms packed within rectangular boundaries. Lionel March and Ray Matela enumerated ‘polyominoes’: arrangements of square cells joined edgewise, starting from the two-celled domino. March collaborated with Christopher Earl on an extremely elegant foundational paper ‘On counting architectural plans’ which dealt with packings of rooms of any shape.

Graph Visions is a history book. Vardouli has done an excellent job. She is fully in command of all the mathematics and computation and has ploughed her way through many dusty, indigestible documents to produce her lucid and attractive account. The book is handsomely presented and illustrated. Her work is in stark contrast to two recent accounts of LUBFS by other historians linked to MIT, who completely misunderstood and misrepresented the research, partly because they did not read the key papers and books. ⁸ Vardouli is particularly good, for instance, on the changes that were taking place in Britain in the 1960s in the teaching of mathematics in school, where the Schools Mathematics Project introduced discrete maths including graph theory into the curriculum. Vardouli argues convincingly that this in turn influenced researchers in architecture. I realised from reading her account about how this might have happened in my own case, which I had not appreciated at the time.

Vardouli’s history stops at the end of the 1970s. For someone who has continued to work on ‘graph vision’ however, the book invites reflections on the later fortunes of these ideas and tools. What happened next? One long-term influence to which Vardouli makes reference is the development of CAD in architecture, not the plan-generating programs, but the all-purpose tools for drafting and modelling that appeared from the 1970s. The symmetry operations in the plane that were explained in The Geometry of Environment were and are basic to the manipulation of shape in 2D drafting systems, while Boolean operations on geometric solids are at the heart of some 3D modellers. As Vardouli indicates in her sub-title, graph and network-based data structures are ‘digital architecture’s skeletons’.

A few of the infrastructures and megastructures dreamed of by Yona Friedman were built, not by him but by Moshe Safdie and others. But the Flatwriter was never put into serious use – and in case Friedman’s command of the mathematics was shaky and approximate. Do many architects still use Alexander’s Pattern Language? The book is sometimes claimed as the most popular work on architecture since Vitruvius; but I have not seen it recently in architecture schools. I imagine that it might not appeal to practitioners, to be confined to features and parts of buildings pre-designed by others.

Work continues to this day on the automated generation of plan layouts by computer, with the goal of minimising pedestrian movement, again with little or no application in practice. The project has never overcome some basic weaknesses. First, if circulation is minimised, then the plans produced tend to be deep concentric clusters of spaces around the most highly connected space – as in Whitehead and Eldars’ work – without any clear structure of corridors and halls, and impossible to light naturally at the centre. Second, the plans tend to be confined to a single storey and cannot cope with the fact that multi-storey buildings have similar plan shapes on successive floors and are strongly constrained by the positions of their vertical circulation. Thirdly, the data on frequency of journeys is drawn from existing buildings; but if a new building has a different geometry, this in itself is likely to change the patterns of people’s movement. Plan geometry and circulation interact.

One notable omission from Graph Vision is the work of Bill Hillier and his ‘space syntax’ group in the Bartlett School at University College London. This must I think be deliberate; perhaps because Hillier’s early work can be more properly described as archaeological and sociological than directly concerned with architectural design. But there was a central concern in space syntax with graph-theoretic representations of building plans, and later of the street networks of cities. The first research was on samples of historical and vernacular house plans, with the purpose of the graph analysis being to separate the access structures from the geometry – as in the Wright plans of Figure 1. Hiller referred to this separation, using a biological analogy, as that between a genotype (the common graph) and phenotypes (individual house plans sharing that graph). The genotype was a mental construct, realised through traditional construction practices, which transmitted the generic plan via cultural evolution and gave rise to the type. Variant phenotypes were found, responding to local conditions, the sizes and shapes of particular sites and so on.

In 1978, Bill Hillier with Paul Stansall and Julienne Hanson produced a report on The Analysis of Complex Buildings that was never published. ⁹ This presented plans of 24 large buildings, from prehistoric examples to a modern school and hospital, with their access graphs. Figure 2 shows an example: the plan and graph of the ground floor of a grand Victorian country mansion, Buchanan House. The rooms are arranged in the graph by ‘depth’, that is, the number of spaces that must be passed through from the entrance to reach the room in question. The analyses offered some fascinating insights into the social organisation and patterns of use of the various building types.

Figure 2.

(a) Plan of Buchanan House, Stirlingshire, 1851–53, and (b) the access graph of this plan, redrawn from Bill Hillier, Paul Stansall and Julienne Hanson, The Analysis of Complex Buildings, 1978, p. 25. The graph is arranged to show the depths of rooms from the exterior, measured by the numbers of intervening spaces, with the deepest rooms at the left.

This line of work on the graphs of larger buildings was not pursued, however. Maybe ‘complex buildings’ were just too complex. What becomes clear is that, besides the constraints of access, the forms of these bigger buildings become crucially limited by what Hillier would call other ‘generic functions’, foremost the provision of natural lighting, as well as clarity and oversight in circulation systems. As with the automated plan layout programs, other basic constraints on building form besides simple accessibility must be taken into account.

As for the methods of exhaustive enumeration of plans, Friedman’s Flatwriter generated non-rectangular layouts for apartments, raising questions about how these were to be packed together into the infrastructures. Meanwhile March and Matela’s polyominoes were quite un-building like in an obvious way: they only allowed rooms to be joined along the whole lengths of their walls, not overlapped. The computer system that Mitchell, Liggett and I devised could generate all plans for small houses or flats, meeting constraints on both the dimensions and the adjacency of spaces expressed as graphs. The plans were perfectly realistic and buildable.

The overriding problem with all these enumeration methods, however, is that they come up against the fact that the number of possible plans grows fast with increasing numbers of rooms – there is a ‘combinatorial explosion’ in the jargon – and beyond say 10 or 15 spaces, complete catalogues become computationally out of the question. Bill Hillier drew the conclusion that architecture is not what Ramon Lull would have called an ars combinatoria. Complete listings of possible building plans are impossible.

Hillier’s point is correct insofar as it relates to representation at the level of individual rooms. But it does not mean that possible plans and built forms cannot be counted at higher levels of abstraction. Marc van Leusen was awarded a doctorate by TU Delft in 1994 for a thesis on A System of Types in the Domain of Residential Buildings. ¹⁰ Van Leusen describes a graph-based method for representing apartment types and the ways in which they can be fitted into blocks with vertical or horizontal circulation. The apartments are represented as ‘floor units’ without any detail of their internal room arrangement. Graphs are used to control the systems of public circulation between apartments and the exterior, not within apartments, and to ensure that apartments are naturally lit from one or two sides. All possibilities are enumerated. Their numbers are quite modest. Here is a sophisticated, realistic, working ‘Flatwriter’.

Van Leusen includes a graphic catalogue showing where the plans of actual apartments that have been built and illustrated in professional handbooks are to be found within this world of theoretical options. Figure 3 shows a sample page of apartment types for blocks with vertical circulation and made from two, three or four ‘floor units’. The boxes in heavy line enclose types found in the published literature. The actual is set against the possible. This comparison raises provocative questions of why some types that are theoretically available have not been adopted in practice. Is this through ignorance perhaps or because architects have applied further criteria for choice that the method does not allow for?

Figure 3.

A page from a complete catalogue of apartment types possible within elongated multi-storey blocks, from Marc van Leusen, A System of Types in the Domain of Residential Buildings, 1994, p. 216. These are types consisting of two, three or four ‘floor units’, in blocks with vertical circulation. The boxes in heavy line contain types that have been built in practice and published in design handbooks. Reproduced by kind permission of Marc van Leusen.

Van Leusen’s work is not as well-known as it should be. I examined a doctoral thesis recently by a student who had built an ingenious computer system for laying out apartments in blocks to order. I asked why should he want to do this, when he could find all the available options in Van Leusen’s catalogue?

I have been working myself in recent decades with my colleague Linda Waddoups on another approach to the exhaustive enumeration of larger rectangular built forms, in our case made up from wings, ranges and courts. ¹¹ Again, the method can be exhaustive because of the representation being made at a higher level. The layout of rooms within floors is not considered. This is not the place to go into detail. Like van Leusen’s work, the plans of real buildings – offices, school and hospitals – can be located within what, borrowing a term from theoretical biology, we have called ‘morphospaces’, spaces of theoretically possible forms. The work is not offered as any kind of design method. My idea is that it might contribute to an architectural science, through an increased understanding of how built form is constrained by generic function; and to a morphological history of architecture, directed at the analysis of building types from a geometrical point of view, and how those types evolve and are transformed.