A multilevel algorithm for force-directed graph drawing

We describe a heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm. The multilevel process groups vertices to form clusters, uses the clusters to define a new graph and is repeated until the graph size falls below some threshold. The coarsest graph is then given an initial layout and the layout is successively refined on all the graphs starting with the coarsest and ending with the original. In this way the multilevel algorithm both accelerates and gives a more global quality to the force- directed placement. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on a number of examples ranging from 500 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 30 seconds for a 10,000 vertex graph to around 10 minutes for the largest graph. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Statistical investigations - drawing it all together

The author's approach to teaching an integrative unit to a small group of master’s level Applied Statistics students in 2000-2001 is described. Details of the various activities such as data analysis, reading and discussion of papers, and training in consultancy skills are given, as also are details of the assessment. The students’ and lecturer’s views of the unit are discussed.

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.

An architectural approach to autonomics and self-management of automotive embedded electronic systems

Embedded electronic systems in vehicles are of rapidly increasing commercial importance for the automotive industry. While current vehicular embedded systems are extremely limited and static, a more dynamic configurable system would greatly simplify the integration work and increase quality of vehicular systems. This brings in features like separation of concerns, customised software configuration for individual vehicles, seamless connectivity, and plug-and-play capability. Furthermore, such a system can also contribute to increased dependability and resource optimization due to its inherent ability to adjust itself dynamically to changes in software, hardware resources, and environment condition. This paper describes the architectural approach to achieving the goals of dynamically self-configuring automotive embedded electronic systems by the EU research project DySCAS. The architecture solution outlined in this paper captures the application and operational contexts, expected features, middleware services, functions and behaviours, as well as the basic mechanisms and technologies. The paper also covers the architecture conceptualization by presenting the rationale, concerning the architecture structuring, control principles, and deployment concept. In this paper, we also present the adopted architecture V&V strategy and discuss some open issues in regards to the industrial acceptance.

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.

Drawing the net: internet identification, internet use, and the image of internet users

Theory and research suggest that Internet identification may account for some of the gender divide in Internet use. Internet identification is a type of domain identification, and is inherently bound with images of those who use the Internet, a domain traditionally conceived as masculine. Combining the “draw an Internet user” test with an Internet identification scale, this study tests two hypotheses: participants drawing gender-concordant images will (i) identify with and (ii) use the Internet more than those drawing gender-discordant images. Participants were 371 students (121 males, 250 females) from three universities in the United Kingdom and Australia. The need to challenge masculinized images of the Internet is discussed.