A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

The 2001 World Trade Centre evacuation

The WTC evacuation of 11 September 2001 provides an unrepeatable opportunity to probe into and understand the very nature of evacuation dynamics and with this improved understanding, contribute to the design of safer, more evacuation efficient, yet highly functional, high rise buildings. Following 9/11 the Fire Safety Engineering Group (FSEG) of the University of Greenwich embarked on a study of survivor experiences from the WTC Twin Towers evacuation. The experiences were collected from published accounts appearing in the print and electronic mass media and are stored in a relational data base specifically developed for this purpose. Using these accounts and other available sources of information FSEG also undertook a series of numerical simulations of the WTC North Tower. This paper represents an overview of the results from both studies.

A computational study of the characteristics of aircraft post-crash fires

Full-scale furnished cabin fires have been studied experimentally for the purpose of characterising the post-crash cabin fire environment by the US Federal Aviation Administration for many years. In this paper the Computational Fluid Dynamics fire field model SMARTFIRE is used to simulate one of these fires conducted in the C-133 test facility in order to provide further validation of the computational approach and the SMARTFIRE software. The experiment involves exposing the interior cabin materials to an external fuel fire, opening only one exit at the far end of the cabin (the same side as the rupture) for ventilation, and noting the subsequent spread of the external fire to the cabin interior and the onset of flashover at approximately 210 seconds. Through this analysis, the software is shown to be in good agreement with the experimental data, producing reasonable agreement with the fire dynamics prior to flashover and producing a reasonable prediction of the flashover time i.e. 225 seconds. The paper then proceeds to utilize the model to examine the impact on flashover time of the extent of cabin furnishings and cabin ventilation provided by available exits

L'histoire assassinee: Manfredo Tafuri and the present

Italian historian Manfredo Tafuri develops his ‘historical project’ in architecture during the 1960’s and 1970’s in three seminal books, which reach the English speaking specialist audience with a certain delay. Histories and Theories of Architecture (1968), which prepares the ground for the redefinition of a critical and independent history of architecture is first translated in English in 1979. Architecture and Utopia (Progetto e utopia, 1973) is translated in 1976, and becomes a point of reference for architectural histories and for the definition of architectural theories, mainly in the United States. The Sphere and the Labyrinth (1980), translated in 1987, is the text which formally defines and presents the ‘historical project’. Tafuri’s dense and highly politicized prose is often subjected in the English versions to numerous simplifications and reductive interpretations. Yet, the time lag and the space between languages that these translations occupy are inhabited by polemical and fertile reactions to the texts from the world of architectural design. Symptomatic of all, Aldo Rossi’s L’architecture assassinée, a rebuke in drawing to some of Tafuri’s remarks in Architecture and Utopia that seemed to suggest -but the interpretation is arguable– the ‘death’ of architecture as project (progetto). Tafuri’s texts instigate a dialogue between architectural history and practice, particularly relevant at a time in the development of the discipline when history was being redefined in its critical role as a ‘project’ –thus appropriating the active and propositional role traditionally assigned to architectural design–, while architectural design –still coping with the legacy of Modernism and with changed production systems- often found itself relegated to the paper of exhibitions, competitions and theoretical projects. This paper explores the relationship between architectural history and design in Tafuri’s work, focusing on recent reconsideration and interpretations of his work. It argues that, beyond instrumental simplifications, Tafuri’s ‘project’ remains active and essential in architecture’s critical culture today.