Publications by Prof Peter Rodgers

Graph drawing, involving the automatic layout of graphs, is vital for clear data visualization and interpretation but poses challenges due to the optimization of a multi-metric objective function, an area where current search-based methods seek improvement. In this paper, we investigate the performance of Jaya algorithm for automatic graph layout with straight lines. Jaya algorithm has not been previously used in the field of graph drawing. Unlike most population-based methods, Jaya algorithm is a parameter-less algorithm in that it requires no algorithm-specific control parameters and only population size and number of iterations need to be specified, which makes it easy for researchers to apply in the field. To improve Jaya algorithm's performance, we applied Latin Hypercube Sampling to initialize the population of individuals so that they widely cover the search space. We developed a visualization tool that simplifies the integration of search methods, allowing for easy performance testing of algorithms on graphs with weighted aesthetic metrics. We benchmarked the Jaya algorithm and its enhanced version against Hill Climbing and Simulated Annealing, commonly used graph-drawing search algorithms which have a limited number of parameters, to demonstrate Jaya algorithm's effectiveness in the field. We conducted experiments on synthetic datasets with varying numbers of nodes and edges using the Erdős–Rényi model and real-world graph datasets and evaluated the quality of the generated layouts, and the performance of the methods based on number of function evaluations. We also conducted a scalability experiment on Jaya algorithm to evaluate its ability to handle large-scale graphs. Our results showed that Jaya algorithm significantly outperforms Hill Climbing and Simulated Annealing in terms of the quality of the generated graph layouts and the speed at which the layouts were produced. Using improved population sampling generated better layouts compared to the original Jaya algorithm using the same number of function evaluations. Moreover, Jaya algorithm was able to draw layouts for graphs with 500 nodes in a reasonable time.

Set systems can be visualized in various ways. An important distinction between techniques is whether the elements have a spatial location that is to be used for the visualization; for example, the elements are cities on a map. Strictly adhering to such location may severely limit the visualization and force overlay, intersections and other forms of clutter. On the other hand, completely ignoring the spatial dimension omits information and may hide spatial patterns in the data. We study layouts for set systems (or hypergraphs) in which spatial locations are displaced onto concentric circles or a grid, to obtain schematic set visualizations. We investigate the tractability of the underlying algorithmic problems adopting different optimization criteria (e.g. crossings or bends) for the layout structure, also known as the support of the hypergraph. Furthermore, we describe a simulated-annealing approach to heuristically optimize a combination of such criteria. Using this method in computational experiments, we explore the trade-offs and dependencies between criteria for computing high-quality schematic set visualizations.

Background: Area-proportional Euler diagrams are frequently used to visualize data from Microarray experiments, but are also applied to a wide variety of other data from biosciences, social networks and other domains. Results: This paper details Edeap, a new simple, scalable method for drawing areaproportional Euler diagrams with ellipses. We use a search-based technique optimizing a multi-criteria objective function that includes measures for both area accuracy and usability, and which can be extended to further user-defned criteria. The Edeap software is available for use on the web, and the code is open source. In addition to describing our system, we present the frst extensive evaluation of software for producing area-proportional Euler diagrams, comparing Edeap to the current state-of-the-art; circle-based method, venneuler, and an alternative ellipse-based method, eulerr. Conclusions: Our evaluation—using data from the Gene Ontology database via GoMiner, Twitter data from the SNAP database, and randomly generated data sets—shows an ordering for accuracy (from best to worst) of eulerr, followed by Edeap and then venneuler. In terms of runtime, the results are reversed with venneuler being the fastest, followed by Edeap and fnally eulerr. Regarding scalability, eulerr cannot draw non-trivial diagrams beyond 11 sets, whereas no such limitation is present in Edeap or venneuler, both of which draw diagrams up to the tested limit of 20 sets.

Free rides and observational advantages occur in visualizations when they reveal facts that must be inferred from an alternative representation. Understanding whether these concepts correspond to cognitive advantages is important: do they facilitate information extraction, saving the `deductive cost' of making inferences? This paper presents the first evaluations of free rides and observational advantages in visualizations of sets compared to text. We found that, for Euler and linear diagrams, free rides and observational advantages yielded significant improvements in task performance. For Venn diagrams, whilst their observational advantages yielded significant performance benefits over text, this was not universally true for free rides. The consequences are two-fold: more research is needed to establish when free rides are beneficial, and the results suggest that observational advantages better explain the cognitive advantages of diagrams over text. A take-away message is that visualizations with observational advantages are likely to be cognitively advantageous over competing representations.

This paper presents an empirical study to determine whether alterations to graphical features (colour and size) of automatically generated LineSets improve task performance. LineSets are used to visualise sets and networks. The increasingly common nature of such data suggests that having effective visualisations is important. Unlike many approaches to set and network visualisation, which often use concave or convex shapes to represent sets alongside graphs, LineSets use lines overlaid on a graph. LineSets have been shown to be advantageous over shape-based approaches. However, the graphical properties of LineSets have not been fully explored. Our results suggest that automatically drawn LineSets can be significantly improved for certain tasks through the considered use of colour alongside size variations applied to their graphical elements. In particular, we show that perceptually distinguishable colours, lines of varying width, and nodes of varying diameter lead to improved task performance in automatically laid-out LineSets.

This paper presents the first empirical investigation that compares Euler and linear diagrams when they are used to represent set cardinality. A common approach is to use area-proportional Euler diagrams but linear diagrams can exploit length-proportional straight-lines for the same purpose. Another common approach is to use numerical annotations. We first conducted two empirical studies, one on Euler diagrams and the other on linear diagrams. These suggest that area-proportional Euler diagrams with numerical annotations and length-proportional linear diagrams without numerical annotations support significantly better task performance. We then conducted a third study to investigate which of these two notations should be used in practice. This suggests that area-proportional Euler diagrams with numerical annotations most effectively supports task performance and so should be used to visualize set cardinalities. However, these studies focused on data that can be visualized reasonably accurately using circles and the results should be taken as valid within that context. Future work needs to determine whether the results generalize both to when circles cannot be used and for other ways of encoding cardinality information.

Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search based methods for graph drawing which are based on optimizing an objective function which is formed from a weighted sum of multiple criteria. In this paper, we propose a new neighbourhood search method which uses a tabu search coupled with path relinking to optimize such objective functions for general graph layouts with undirected straight lines. To our knowledge, before our work, neither of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimization techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (objective function's value) and the speed of layout in terms of the number of evaluated solutions required to draw a graph. We also examine the relative scalability of each method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can layout larger graphs than the state-of-the-art neighbourhood search methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset.

This paper addresses the problem of how best to visualize network data grouped into overlapping sets. We address it by evaluating various existing techniques alongside a new technique. Such data arise in many areas, including social network analysis, gene expression data, and crime analysis. We begin by investigating the strengths and weakness of four existing techniques, namely Bubble Sets, EulerView, KelpFusion, and LineSets, using principles from psychology and known layout guides. Using insights gained, we propose a new technique, SetNet, that may overcome limitations of earlier methods. We conducted a comparative crowdsourced user study to evaluate all five techniques based on tasks that require information from both the network and the sets. We established that EulerView and SetNet, both of which draw the sets first, yield significantly faster user responses than Bubble Sets, KelpFusion and LineSets, all of which draw the network first.

Sets comprise a generic data model that has been used in a variety of data analysis problems. Such problems involve analysing and visualizing set relations between multiple sets defined over the same collection of elements. However, visualizing sets is a non-trivial problem due to the large number of possible relations between them. We provide a systematic overview of state-of-the-art techniques for visualizing different kinds of set relations. We classify these techniques into six main categories according to the visual representations they use and the tasks they support. We compare the categories to provide guidance for choosing an appropriate technique for a given problem. Finally, we identify challenges in this area that need further research and propose possible directions to address these challenges. Further resources on set visualization are available at http://www.setviz.net.

This paper presents the first design principles that optimize the visualization of sets using linear diagrams. These principles are justified through empirical studies that evaluate the impact of graphical features on task performance. Linear diagrams represent sets using straight line segments, with line overlaps corresponding to set intersections. This work builds on recent empirical research which establishes that linear diagrams can be superior to prominent set visualization techniques, namely Euler and Venn diagrams. We address the problem of how to best visualize overlapping sets using linear diagrams. To solve the problem, we investigate which graphical features of linear diagrams significantly impact user task performance. To this end, we conducted seven crowd-sourced empirical studies involving a total of 1760 participants. These studies allowed us to identify the following design principles, which significantly aid task performance: use a minimal number of line segments, use guide-lines where overlaps start and end, and draw lines that are thin as opposed to thick bars. We also evaluated the following graphical properties which did not significantl impact task performance: colour, orientation, and set-order. The results are brought to life through a freely available software implementation that automatically draws linear diagrams with user-controlled graphical choices. An important consequence of our research is that users are now able to create effective visualizations of sets automatically, thus improving human-computer interaction.

This paper reports on a method to improve the automated layout of schematic diagrams by widening the search space examined by the system. In search-based layout methods there are typically a number of parameters that control the search algorithm which do not affect the fitness function, but nevertheless have an impact on the final layout. We explore how varying three parameters (grid spacing, the starting distance of allowed node movement and the number of iterations) affects the resultant diagram in a hill- climbing layout system. Using an iterative process, we produce diagram layouts that are significantly better than those produced by ad-hoc parameter settings.

The least cognitively demanding way to create a diagram is to draw it with a pen. Yet there is also a need for more formal visualizations, that is diagrams created using both traditional keyboard and mouse interaction. Our objective is to allow the creation of diagrams using traditional and stylus-based input. Having two diagram creation interfaces requires that changes to a diagram should be automatically rendered in the other visualization. Because sketches are imprecise, there is always the possibility that conversion between visualizations results in a lack of syntactic consistency between the two visualizations. We propose methods for converting diagrams between forms, checking them for equivalence and rectifying inconsistencies. As a result of our theoretical contributions, we present an intelligent software system allowing users to create and edit diagrams in sketch or formal mode. Our proof of concept tool supports diagrams with connected and spatial syntactic elements. Two user studies show that this approach is viable and participants found the software easy to use. We conclude that supporting such diagram creation is now possible in practice.

This paper establishes the impact of topological and graphical properties on the comprehension of Euler diagrams. To-date, various studies have examined the impact of individual properties of Euler diagrams, such as curve shape and orientation. This has allowed us to establish guides for using these properties such as 'draw Euler diagrams with circles' and 'draw Euler diagrams without regard to orientation'. However, until the work described here, questions still remain, for example 'do these guides, when combined, make a significant difference to real-world Euler diagrams?', and if so, 'should they be used by those visualising set data with Euler diagrams?' To answer these questions an empirical study was conducted to compare Euler diagrams that have been drawn by others for their real-world data, against versions that adhere to all of the guides in combination. The study establishes that both the accuracy and the speed with which information is derived from Euler diagrams is significantly improved when Euler diagrams adhere, where possible, to all the guides. The improvement is considerable when using the guided diagrams, with on average, the error rate being more than halved from 21.4% to 10.3%, and a 9 s improvement in the average time taken, from 34.2s to 24.9s. As Euler diagrams are regularly used to visualise information in a multitude of areas, ranging from crime control to social network analysis, our results indicate that applying the guides to these diagrams will improve the ability of users to accurately and quickly extract information.

Euler diagrams use closed curves to represent sets and their relationships. They facilitate set analysis, as humans tend to perceive distinct regions when closed curves are drawn on a plane. However, current automatic methods often produce diagrams with irregular, non-smooth curves that are not easily distinguishable. Other methods restrict the shape of the curve to for instance a circle, but such methods cannot draw an Euler diagram with exactly the required curve intersections for any set relations. In this paper, we present eulerForce, as the first method to adopt a force-directed approach to improve the layout and the curves of Euler diagrams generated by current methods. The layouts are improved in quick time. Our evaluation of eulerForce indicates the benefits of a force-directed approach to generate comprehensible Euler diagrams for any set relations in relatively fast time.

Linear diagrams have recently been shown to be more effective than Euler diagrams when used for set-based reasoning. However, unlike the growing corpus of knowledge about formal aspects of Euler and Venn diagrams, there has been no formalisation of linear diagrams. To fill this knowledge gap, we present and formalise Point and Line (PaL) diagrams, an extension of simple linear diagrams containing points, thus providing a formal foundation for an effective visual language.We prove that PaL diagrams are exactly as expressive as monadic first-order logic with equality, gaining, as a corollary, an equivalence with the Euler diagram extension called spider diagrams. The method of proof provides translations between PaL diagrams and sentences of monadic first-order logic.

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts.We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.

Venn diagrams with three curves are used extensively in various medical and scientific disciplines to visualize relationships between data sets and facilitate data analysis. The area of the regions formed by the overlapping curves is often directly proportional to the cardinality of the depicted set relation or any other related quantitative data. Drawing these diagrams manually is difficult and current automatic drawing methods do not always produce appropriate diagrams. Most methods depict the data sets as circles, as they perceptually pop out as complete distinct objects due to their smoothness and regularity. However, circles cannot draw accurate diagrams for most 3-set data and so the generated diagrams often have misleading region areas. Other methods use polygons to draw accurate diagrams. However, polygons are non-smooth and non-symmetric, so the curves are not easily distinguishable and the diagrams are difficult to comprehend. Ellipses are more flexible than circles and are similarly smooth, but none of the current automatic drawing methods use ellipses. We present eulerAPE as the first method and software that uses ellipses for automatically drawing accurate area-proportional Venn diagrams for 3-set data. We describe the drawing method adopted by eulerAPE and we discuss our evaluation of the effectiveness of eulerAPE and ellipses for drawing random 3-set data. We compare eulerAPE and various other methods that are currently available and we discuss differences between their generated diagrams in terms of accuracy and ease of understanding for real world data.

Euler diagrams visually represent containment, inpresstersection and exclusion using closed curves. They first appeared several hundred years ago, however, there has been a resurgence in Euler diagram research in the twenty-first century. This was initially driven by their use in visual languages, where they can be used to represent logical expressions diagrammatically. This work lead to the requirement to automatically generate Euler diagrams from an abstract description. The ability to generate diagrams has accelerated their use in information visualization, both in the standard case where multiple grouping of data items inside curves is required and in the area-proportional case where the area of curve intersections is important. As a result, examining the usability of Euler diagrams has become an important aspect of this research. Usability has been investigated by empirical studies, but much research has concentrated on wellformedness, which concerns how curves and other features of the diagram interrelate. This work has revealed the drawability of Euler diagrams under various wellformedness properties and has developed embedding methods that meet these properties. Euler diagram research surveyed in this paper includes theoretical results, generation techniques, transformation methods and the development of automated reasoning systems for Euler diagrams. It also overviews application areas and the ways in which Euler diagrams have been extended.

3D Euler diagrams visually represent the set-theoretic notions of intersection, containment and disjointness by using closed, orientable surfaces. In previous work, we introduced 3D Venn and Euler diagrams and formally defined them. In this paper, we consider the drawability of data sets using 3D Venn and Euler diagrams. The specific contributions are as follows. First, we demonstrate that there is more choice of layout when drawing 3D Euler diagrams than when drawing 3D Euler diagrams. These choices impact the topological adjacency properties of the diagrams and having more choice is helpful for some Euler diagram drawing algorithms. To illustrate this, we consider the well-known class of Venn-3 diagrams in detail. We then proceed to consider drawability questions centered around which data sets can be visualized when the diagrams are required to possess certain properties. We show that any diagram description can be drawn with 3D Euler diagrams that have unique labels. We then go on to define a set of necessary and sufficient conditions for wellformed drawability in 3D.

Area-proportional Euler diagrams representing three sets are commonly used to visualize the results of medical experiments, business data, and information from other applications where statistical results are best shown using interlinking curves. Currently, there is no tool that will reliably visualize exact area-proportional diagrams for up to three sets. Limited success, in terms of diagram accuracy, has been achieved for a small number of cases, such as Venn-2 and Venn-3 where all intersections between the sets must be represented. Euler diagrams do not have to include all intersections and so permit the visualization of cases where some intersections have a zero value. This paper describes a general, implemented, method for visualizing all 40 Euler-3 diagrams in an area-proportional manner. We provide techniques for generating the curves with circles and convex polygons, analyze the drawability of data with these shapes, and give a mechanism for deciding whether such data can be drawn with circles. For the cases where non-convex curves are necessary, our method draws an appropriate diagram using non-convex polygons. Thus, we are now always able to automatically visualize data for up to three sets.

Haptic devices are becoming more widely used as hardware becomes available and the cost of both low and high fidelity haptic devices decreases. One of the application areas of haptics is Haptic Data Visualization (HDV). HDV provides functionality by which users can feel and touch data. Blind and partially sighted users can benefit from HDV, as it helps them manipulate and understand information. However, developing any three-dimensional haptic world is difficult, time-consuming and requires skilled programmers. Therefore, systems that enable haptic worlds to be rapidly developed in a simple environment could enable non-computer skilled users to create haptic 3D interactions. In this article we present HITPROTO: a system that enables users, such as mentors or support workers, to quickly create haptic interactions (with an emphasis on HDVs) through a visual programming interface. We describe HITPROTO and include details of the design and implementation. We present the results of a detailed study using postgraduate students as potential mentors, which provides evidence of the usability of HITPROTO. We also present a pilot study of HITPROTO with a blind user. It can be difficult to create prototyping tools and support 3D interactions, therefore we present a detailed list of 'lessons learnt' that provides a set of guidelines for developers of other 3D haptic prototyping tools.

Euler diagrams are often used to visualize intersecting data sets in applications such as criminology; genetics, medicine, and computer file systems. One interesting aspect of these diagrams is that some data sets cannot be drawn without breaking one or more ''wellformedness properties, which are considered to reduce the user comprehension of the diagrams. However, it is possible to draw the same data with different diagrams, each of which breaks different wellformedness properties. Hence, some properties are ''swappable, so motivating the study of which of the alternatives would be best to use. This paper reports on the two empirical studies to determine how wellformedness properties affect comprehension. One study was with abstract data, the other was with concrete data that visualized students' enrollment on university modules. We have results from both studies that imply that diagrams with concurrency or disconnected zones perform less well than other some other properties. Further, we have no results that imply that diagrams with brushing points adversely affect performance. Our data also indicate that nonsimple curves are preferred less than diagrams with other properties. These results will inform both human diagram designers and the developers of automated drawing systems on the best way to visualize data using Euler diagrams.

Euler diagrams are used for visualizing categorized data. These categories, together with information about when categories share some datum, can be turned into a succinct diagram description from which an Euler diagram can be generated. Closed curves represent the categories and the relationships between the curves (such as containment) correspond to relationships between the categories (such as subset). A range of automated Euler diagram drawing methods have been proposed but they often produce diagrams that are aesthetically unpleasing, can be computationally complex and most of them cannot draw a diagram for some (often many) given collections of categories. One such method is capable of drawing aesthetically pleasing Euler diagrams, using only circles, and is computationally efficient (being of polynomial time complexity) but it applies to a very restricted subset of collections of categorized data. This paper substantially extends that method so it can always draw an Euler diagram, that is it applies to all collections of categorized data. In particular, we identify a class of diagram descriptions that can be drawn with circles, generalizing previous work. For diagram descriptions outside of this class, we define transformations that can be used to turn them into descriptions inside the drawable with circles class. We demonstrate how such transformations can be done in a general, a process during which many choices must be made. Further, we provide strategies for making particular choices which ensure desirable properties, such as curve containment, are preserved. We have provided a software implementation of the drawing method, which is freely available from www.eulerdiagrams.com/inductivecircles.htm.

Area-proportional Euler diagrams have many applications, for example they are often used for visualizing data in medical and biological domains. There have been a number of recent research efforts to automatically draw Euler diagrams when the areas of the regions are not considered, leading to a range of different drawing techniques. By contrast, substantially less progress has been made on the problem of automatically drawing area-proportional Euler diagrams, although some partial results have been derived. In this paper, we considerably advance the state-of-the-art in area-proportional Euler diagram drawing by presenting the first method that is capable of generating such a diagram given any area-proportional specification. Moreover, our drawing method is sufficiently flexible that it allows one to specify which of the typically enforced wellformedness conditions should be possessed by the to-be-drawn Euler diagram.

Euler diagrams are effective tools for visualizing set intersections. They have a large number of application areas ranging from statistical data analysis to software engineering. However, the automated generation of Euler diagrams has never been easy: given an abstract description of a required Euler diagram, it is computationally expensive to generate the diagram. Moreover, the generated diagrams represent sets by polygons, sometimes with quite irregular shapes which make the diagrams less comprehensible. In this paper we address these two issues by developing the theory of piercings, where we define single piercing curves and double piercing curves. We prove that if a diagram can be built inductively by successively adding piercing curves under certain constraints then it can be drawn with circles, which are more aesthetically pleasing than arbitrary polygons. The theory of piercings is developed at the abstract level. In addition, we present a Java implementation that, given an inductively pierced abstract description, generates an Euler diagram consisting only of circles within polynomial time.

Euler diagrams have a wide variety of uses, from information visualization to logical reasoning. In all of their application areas, the ability to automatically layout Euler diagrams brings considerable benefits. In this paper, we present a novel approach to Euler diagram generation. We develop certain graphs associated with Euler diagrams in order to allow curves to be added by finding cycles in these graphs. This permits us to build Euler diagrams inductively, adding one curve at a time. Our technique is adaptable, allowing the easy specification, and enforcement, of sets of wellformednesss conditions; we present a series of results that identify properties of cycles that correspond to the wellformedness conditions. This improves upon other contributions towards the automated generation of Euler diagrams which implicitly assume some fixed set of wellformedness conditions must hold. In addition, unlike most of these other generation methods, our technique allows any abstract description to be drawn as an Euler diagram. To establish the utility of the approach, a prototype implementation has been developed.

This paper describes an automatic mechanism for drawing metro maps. We apply multicriteria optimization to find effective placement of stations with a good line layout and to label the map unambiguously. A number of metrics are defined, which are used in a weighted sum to find a fitness value for a layout of the map. A hill climbing optimizer is used to reduce the fitness value, and find improved map layouts. To avoid local minima, we apply clustering techniques to the map the hill climber moves both stations and clusters when finding improved layouts. We show the method applied to a number of metro maps, and describe an empirical study that provides some quantitative evidence that automatically-drawn metro maps can help users to find routes more efficiently than either published maps or undistorted maps. Moreover, we found that, in these cases, study subjects indicate a preference for automatically-drawn maps over the alternatives.

Euler diagrams have numerous application areas, with a large variety of languages based on them. In relation to software engineering, such areas encompass modelling and specification including from a formal perspective. In all of these application areas, it is desirable to provide tools to layout Euler diagrams, ideally in a nice way. Various notions of niceness can be correlated with certain properties that an Euler diagram may or may not possess. Indeed, the relevant layout algorithms developed to date produce Euler diagrams that have certain sets of properties, sometimes called well-formedness conditions. However, there is not a commonly agreed definition of an Euler diagram and the properties imposed on them are rarely stated precisely. In this paper, we provide a very general definition of an Euler diagram, which can be constrained in varying ways in order to match the variety of definitions that exist in the literature. Indeed, the constraints imposed correspond to properties that the diagrams may possess. A contribution of this paper is to provide formal definitions of these properties and we discuss when these properties may be desirable. Our definition of an Euler diagram and the formalization of these properties provides a general language for the Euler diagram community to utilize. A consequence of using a common language will be better integration of, and more accessible, research results.

Jonathan Roberts, Nadia Boukhelifa, Peter Rodgers have developed a system that can visualize search-result data using glyphs and coordinated multiple-views. They stress a need for a web-search result visualization as the rank-ordered lists of search results allow the user view only a small proportion of the results in a single window. Some of the glyphs show the domain of the site of each webpage (with the addresses: .country, .com, .edu, .org, or .net mapped to triangle, circle, square, parallelogram, hexagon, plus-symbol, respectively), where the rank is allocated a color (with a brighter color representing a higher ranked entity) and the size of the page relates to the border-width of the glyph. Another glyph design is based on quartiles (with the use of color, placement, and concentric rings) and allowed to assign the quantities to the lower, median or upper quartile or represent the measure of external and internal links of a site placement.

This paper describes a model for expressing coordination in multiple view visualization systems. We present the model and describe a prototype implementation that illustrates the features of the model. Current visualization systems tend to have an informal and inconsistent approach to coordination, so our model is an attempt to put widely used coordination concepts on a more formal footing. The model is based on views sharing abstract objects that contain dataflow parameters and describes how current coordinations in exploratory visualization work and allows novel coordinations to be constructed.

We describe GATE, the General Architecture for Text Engineering, an integrated visual development environment to support the visual assembly, execution and analysis of modular natural language processing systems. The visual model is an executable data flow program graph, automatically synthesised from data dependency declarations of language processing modules. The graph is then directly executable: modules are run interactively in the graph, and results are accessible via generic text visualisation tools linked to the modules. These tools lighten the cognitive load of viewing and compar-ing module results by relating data produced by modules back to the underlying text, by reducing the amount of search in examining results, and by displaying results in context. Overall, the GATE integrated visual development environment leads to rapid understanding of system behaviour and hence to rapid system refinement, therefore demonstrating the utility of visual programming and visualisation techniques for the development of natural language processing systems.

Textual database programming languages are computationally complete, but have the disadvantage of giving the user a non-intuitive view of the database information that is being manipulated. Visual languages developed in recent years have allowed naive users access to a direct representation of data, often in a graph form, but have concentrated on user interface rather than complex programming tasks. There is a need for a system which combines the advantages of both these programming methods. We describe an implementation of Spider, an experimental visual database programming language aimed at programmers. It uses a graph rewriting paradigm as a basis for a fully visual, computationally complete language. The graphs it rewrites represent the schema and instances of a database. The unique graph rewriting method used by Spider has syntactic and semantic simplicity. Its form of algorithmic expression allows complex computation to be easily represented in short programs. Furthermore, Spider has greater power than normally provided in textual systems, and we show that queries on the schema and associative queries can be performed easily and without requiring any additions to the language.

During the last decade numerous geovisualization tools have been developed, many with highly interactive and manipulable interfaces. And yet we continue to build new tools using a range of technologies and techniques. Why do we invent new instruments? Or why do we need to invent new instruments? There are many possible motivations: 1) New technology continues to appear and it often enables us to do things that were not possible before. 2) We may be able to acquire data of new form or quality that cannot be analysed with existing tools as the data sets may be so large, dense or contain so many dimensions that no current tool supports interactive investigation effectively. 3) As geovisualization is used by a wider range of users, we encounter new tasks that cannot be performed using existing tools. 4) The particular needs of specific users (from this growing user base) are likely to vary. 5) Accessing expertise from different disciplines to our own might contribute to what already exists and enhance it further. 6) Collaboration between researchers may improve our ability to visualize geographic information and to develop the various instruments that support this process. The notion of interoperability underlies our efforts to develop and incorporate ideas and generate knowledge from our data using instruments for ideation. Ideation relates to the formation of ideas and concepts, the end goal of geovisualizers. Today there are many tools and techniques for creating instruments for ideation - sophisticated hardware, advanced programming languages, graphics libraries, visual programming systems and complex GUIs. In each, the developer or visualizer wishes to generate effective interactive graphic realizations of their data that are useful to them and/or their users. Indeed, these geovisualizers will come across many challenges. Above we suggested six factors that explain why new tools and techniques may be developed. In this chapter we expand upon these ideas and consider how each of these issues influence and shape the way we use and develop software for geovisualization.

Geovisualizers often need to represent data that consists of items related together. Such data sets can be abstracted to a mathematical structure, the graph. A graph contains nodes and edges where the nodes represent the items or concepts of interest, and the edges connect two nodes together according to some associational scheme. Examples of graph data include: network topologies; maps, where nodes represent towns and edges represent roads; and social diagrams where people are the nodes and edges represent some relationship between people, for instance, that they are friends. A good layout allows users to more easily investigate the data when performing tasks such as following paths, seeing clusters of closely related nodes and discovering general structures in data. Laying out graphs by hand is time consuming, however there are a number of proven graph drawing methods which can be used to automatically visualize the data.

A key feature of diagrams is well-matchedness, referred to as iconicity in philosophy. A well-matched diagram has a structural resemblance to its semantics and is believed to be an effective representation. In this paper, we view well-matchedness as a feature of diagrams' meaning carriers { syntactic relationships that convey meaning. Each meaning carrier may or may not structurally resemble, i.e. be well-matched to, its semantics. This paper provides the first empirical study that evaluates the impact of well-matched meaning carriers on effectiveness in Euler diagrams and linear diagrams. There are two key take-away messages: using only well-matched meaning carriers led to the best task performance and using both well-matched and non-well-matched meaning carriers in a single diagram should be approached with caution.

A consideration for any visualization technique is the added value it brings over other representations of data. A free ride, a concept introduced by Shimojima, occurs in a visualization when it reveals some fact that must be inferred from an alternative representation from which the visualization was derived. This paper presents preliminary results from an empirical evaluation of free rides occurring in visualizations of sets as compared to textual representations. By focusing on Euler, linear and Venn diagrams, our results suggest that more research is needed to establish when free rides are cognitively beneficial.

Sets can be visualized in various ways and settings. An important distinction between techniques is based on whether the elements have a spatial location that is to be used for the visualization; for example, the elements are cities on a map. Strictly adhering to such location may severely limit the visualization and force overlay, intersections and other forms of clutter. On the other hand, completely ignoring the spatial dimension omits information and may hide spatial patterns in the data. In this abstract, we present ongoing research on a method that is in between spatial and nonspatial visualizations. The main idea is to schematize (move) the spatial locations onto concentric circles, to improve the visualization of the set system while roughly maintaining spatial structure.

Does the choice of colour-coding scheme affect the usability of metro maps, as measured by the accuracy and speed of navigation? Using colour to differentiate lines or services in maps of metro rail networks has been a common practice around the world for many decades. Broadly speaking, there are two basic schemes: 'route colouring', in which each end-to-end route has a distinct colour, and 'trunk colouring', in which each major trunk has a distinct colour, and the individual routes inherit the colour of the main trunk that they run along. A third, intermediate scheme is 'shaded colouring', in which each trunk has a distinct colour, and each route has a distinct shade of that colour. In this study, 285 volunteers in the US were randomised to these three colour-coding schemes and performed seventeen navigational tasks. Each task involved tracing a route in the New York City subway map. Overall, we found that route colouring was significantly more accurate than the trunk- and shaded-colouring schemes. A planned subset analysis, however, revealed major differences between specific navigational hazards: route colouring performed better only against certain navigational hazards; trunk colouring performed best against one hazard; and other hazards showed no effect of colour coding. Route colouring was significantly faster only in one subset.

LineSets represent information about sets by drawing one line for each set on an existing visualization of data items. This paper addresses the following question: does manipulating the size of visual elements affect the comprehension of LineSets? We empirically evaluated two types of size treatments applied to LineSets drawn on networks: varying set-line thickness, to reflect relative set cardinality, and varying node diameter, to reflect data items' relative degree of connectivity. The evaluation required participants to perform tasks that were thought to be aided by the size variations alongside tasks where no benefit was anticipated. Viewing comprehension through accuracy and time performance, we found that varying set-line thickness and node diameter significantly improves the effectiveness of LineSets. As a consequence, this research leads to the recommendation that LineSets vary sizes of lines and nodes.

There are a number of graphical choices to be made when drawing LineSets; one of these choices is colour. This paper identifies how colour (hue, value, or monochrome) should be applied to LineSets drawn on networks.

Euler diagrams are often used for visualizing data collected into sets. However, there is a significant lack of guidance regarding graphical choices for Euler diagram layout. To address this deficiency, this paper asks the question `does the shape of a closed curve affect a user's comprehension of an Euler diagram?' By empirical study, we establish that curve shape does indeed impact on understandability. Our analysis of performance data indicates that circles perform best, followed by squares, with ellipses and rectangles jointly performing worst. We conclude that, where possible, circles should be used to draw effective Euler diagrams. Further, the ability to discriminate curves from zones and the symmetry of the curve shapes is argued to be important. We utilize perceptual theory to explain these results. As a consequence of this research, improved diagram layout decisions can be made for Euler diagrams whether they are manually or automatically drawn.

We present an algorithm for automatically laying out metro map style schematics using a force-directed approach, where we use a localized version of the standard spring embedder forces combined with an octilinear magnetic force. The two types of forces used during layout are naturally conflicting, and the existing method of simply combining these to generate a resultant force does not give satisfactory results. Hence we vary the forces, emphasizing the standard forces in the beginning to produce a well distributed graph, with the octilinear forces becoming prevalent at the end of the layout, to ensure that the key requirement of line angles at intervals of 45? is obtained. Our method is considerably faster than the more commonly used search-based approaches, and we believe the results are superior to the previous force-directed approach. We have further developed this technique to address the issues of dynamic schematic layout. We use a Delaunay triangulation to construct a schematic "frame", which is used to retain relative node positions and permits full control of the level of mental map preservation. This technique is the first to combine mental map preservation techniques with the additional layout criteria of schematic diagrams. To conclude, we present the results of a study to investigate the relationship between the level of mental map preservation and the user response time and accuracy.

Ellipses generate accurate area-proportional Euler diagrams for more data than is possible with circles. However, computing the region areas is difficult as ellipses have various degrees of freedom. Numerical methods could be used, but approximation errors are introduced. Current analytic methods are limited to computing the area of only two overlapping ellipses, but area-proportional Euler diagrams in diverse application areas often have three curves. This paper provides an overview of different methods that could be used to compute the region areas of Euler diagrams drawn with ellipses. We also detail two novel analytic algorithms to instantaneously compute the exact region areas of three general overlapping ellipses. One of the algorithms decomposes the region of interest into ellipse segments, while the other uses integral calculus. Both methods perform equally well with respect to accuracy and time.

There are a range of diagram types that can be used to visualize sets. However, there is a significant lack of insight into which is the most effective visualization. To address this knowledge gap, this paper empirically evaluates four diagram types: Venn diagrams, Euler diagrams with shading, Euler diagrams without shading, and the less well-known linear diagrams. By collecting performance data (time to complete tasks and error rate), through crowdsourcing, we establish that linear diagrams outperform the other three diagram types in terms of both task completion time and number of errors. Venn diagrams perform worst from both perspectives. Thus, we provide evidence that linear diagrams are the most effective of these four diagram types for representing sets.

A variety of data analysis problems can be modelled by defining multiple sets over a collection of elements and analyzing the relations between these sets. Despite their simple concept, visualizing sets is a non-trivial problem due to the large number of possible relations between them. We provide a systematic overview of state-of-the-art techniques for visualizing different kinds of set relations. We classify these techniques into 7 main categories according to the visual representations they use and the tasks they support. We compare the categories to provide guidance for choosing an appropriate technique for a given problem. Finally, we identify challenges in this area that need further research and propose possible directions to address with these challenges.

This paper addresses the problem of how best to use colour in Euler diagrams. The choice of using coloured curves, rather than black curves, possibly with coloured fill is often made in tools that automatically draw Euler diagrams for information visualization as well as when they are drawn manually. We address the problem by empirically evaluating various different colour treatments: coloured or black curves combined with either no fill or coloured fill. By collecting performance data, we conclude that Euler diagrams with coloured curves and no fill significantly outperform all other colour treatments. Most automated layout algorithms adopt colour fill and are, thus, reducing the effectiveness of the Euler diagrams produced. As Euler diagrams can be used in a multitude of areas, ranging from crime control to social network analysis, our results stand to increase the ability of users to accurately and quickly extract information from their visualizations.

In search-based graph drawing methods there are typically a number of parameters that control the search algorithm. These parameters do not affect the ?tness function, but nevertheless have an impact on the ?nal layout. One such search method is hill climbing, and, in the context of schematic layout, we explore how varying three parameters (grid spacing, the starting distance of allowed node movement and the number of iterations) affects the resultant diagram. Although we cannot characterize schematics completely and so cannot yet automatically assign parameters for diagrams, we observe that when parameters are set to values that increase the search space, they also tend to improve the ?nal layout. We come to the conclusion that hillclimbing methods for schematic layout are more prone to reaching local optima than had previously been expected and that a wider search, as described in this paper, can mitigate this, so resulting in a better layout.

This paper describes a prototype visualization system for concurrent and distributed applications programmed using Erlang, providing two levels of granularity of view. Both visualizations are animated to show the dynamics of aspects of the computation. At the low level, we show the concurrent behaviour of the Erlang schedulers on a single instance of the Erlang virtual machine, which we call an Erlang node. Typically there will be one scheduler per core on a multicore system. Each scheduler maintains a run queue of processes to execute, and we visualize the migration of Erlang concurrent processes from one run queue to another as work is redistributed to fully exploit the hardware. The schedulers are shown as a graph with a circular layout. Next to each scheduler we draw a variable length bar indicating the current size of the run queue for the scheduler. At the high level, we visualize the distributed aspects of the system, showing interactions between Erlang nodes as a dynamic graph drawn with a force model. Speci?cally we show message passing between nodes as edges and lay out nodes according to their current connections. In addition, we also show the grouping of nodes into "s_groups" using an Euler diagram drawn with circles.

The graphical choices made when laying out Euler diagrams impact upon both aesthetic quality and comprehensiveness. Graphical choices include the shape, size and colour of closed curves which are commonly described as retinal variables to which we are known to be perceptually sensitive. There is copious literature providing guidance as to how best use retinal variables to visualise both quantitative and qualitative information for a wide range range of diagram types. Further, this guidance is explicitly defined to optimise the users' comprehension of such information. However, there exists little, if any, literature affording guidance as to how best to use retinal variables when laying out Euler diagrams. Here we present a novel insight as to where retinal variables manifest in Euler diagrams, how they might influence our perception of Euler diagrams and, as a consequence, provide motivation and guidance for establishing layout guidelines.

Area-proportional Venn diagrams, where region areas correspond to user-specified values, represent data set relationships intuitively. Circles cannot draw accurate diagrams for most region areas and, polygons have jagged edges that impede understanding. Ellipses have various degrees of freedom and are smooth, but using them to draw such diagrams is challenging. We present eulerAPE: the first software that draws exact area-proportional Venn-3 diagrams using ellipses, for 85% of random data sets.

Euler diagrams, which form the basis of numerous visual languages, can be an effective representation of information when they are both well-matched and well-formed. However, being well-matched and well-formed alone does not imply effectiveness. Other diagrammatical properties need to be considered. Information visualization theorists have known for some time that orientation has the potential to affect our interpretation of diagrams. This paper begins by explaining why well-matched and well-formed drawing principles are insufficient and discusses why we should study the orientation of Euler diagrams. To this end an empirical study is presented, designed to observe the effect of orientation upon the comprehension of Euler diagrams. The paper concludes that the orientation of Euler diagrams does not significantly affect comprehension.

In 2D, Venn and Euler diagrams consist of labelled simple closed curves and have been widely studied. The advent of 3D display and interaction mechanisms means that extending these diagrams to 3D is now feasible. However, 3D versions of these diagrams have not yet been examined. Here, we begin the investigation into 3D Euler diagrams by defining them to comprise of labelled, orientable closed surfaces. As in 2D, these 3D Euler diagrams visually represent the set-theoretic notions of intersection, containment and disjointness. We extend the concept of wellformedness to the 3D case and compare it to wellformedness in the 2D case. In particular, we demonstrate that some data can be visualized with wellformed 3D diagrams that cannot be visualized with wellformed 2D diagrams. We also note that whilst there is only one topologically distinct embedding of wellformed Venn-3 in 2D, there are four such em- beddings in 3D when the surfaces are topologically equivalent to spheres. Furthermore, we hypothesize that all data sets can be visualized with 3D Euler diagrams whereas this is not the case for 2D Euler diagrams, unless non-simple curves and/or duplicated labels are permitted. As this paper is the first to consider 3D Venn and Euler diagrams, we include a set of open problems and conjectures to stimulate further research.

The use of Euler diagrams as a basis for visual languages is commonplace and they are often used for visualizing information. The ability to automatically draw these diagrams is, therefore, likely to be of widespread practical use. The Euler diagram drawing problem is recognized as challenging, but the potential pay-off from the derivation of a comprehensive solution, that produces usable and effective diagrams, is significant. Previous research on automated Euler diagram drawing has used various different approaches, each of which had their own problems, including: (a) failure to draw a diagram in all cases, (b) poor diagram layout, and (c) inability to ensure that certain wellformedness properties of the drawn diagrams hold. In this paper, we present a novel approach to Euler diagram drawing that draws diagrams with circles, ellipses and curves in general. This new approach will draw a diagram in all cases, avoiding bad layout where possible (by the use of nice geometric shapes) and can enforce wellformedness properties as chosen by the user.

Euler diagrams form the basis of various visual languages but tool support for creating them is generally limited to generic diagram editing software using mouse and keyboard interaction. A more natural and convenient mode of entry is via a sketching interface which facilitates greater cognitive focus on the task of diagram creation. Previous work has developed sketching interfaces for Euler diagrams drawn with ellipses. This paper presents SketchSet, the first sketch tool for Euler diagrams whose curves can be circles, ellipses, or arbitrary shapes. SketchSet allows the creation of formal diagrams via point and click interaction. The user drawn diagram, in sketched or formal format, is automatically converted to a diagram in the other format, thus maintaining both views. We provide a mechanism that allows semantic differences between the sketch and the formal diagram to be rectified automatically. Finally, we present a user study that evaluates the effectiveness of the tool.

We present a system for drawing metro map style schematics using a gesture-based interface. This work brings together techniques in gesture recognition on touch-sensitive devices with research in schematic layout of networks. The software allows users to create and edit schematic networks, and provides an automated layout method for improving the appearance of the schematic. A case study using the metro map metaphor to visualize social networks and web site structure is described.

Euler diagrams form the basis of a number of visual languages. However, the existing tool support for creating Euler diagrams is limited to generic diagram editing software that uses mouse and keyboard interfaces. A more natural and convenient mode of entry is via a sketching interface. In addition, it is known that sketching, as opposed to using an editing package, facilitates greater cognitive focus on the task of diagram creation. This paper presents the first sketch tool for Euler diagrams. In particular, we describe the recognition mechanism and conversion that takes a sketched Euler diagram and converts it into a formal diagram drawn with ellipses and circles. The semantics of the sketch is computed.

Euler diagrams are frequently used for visualizing information about collections of objects and form an important component of various visual languages. Properties possessed by Euler diagrams correlate with their usability, such as whether the diagram has only simple curves or possesses concurrency. Sometimes, every diagram that represents some given information possesses some undesirable properties, and reducing the number of violations of undesirable properties is beneficial. In this paper we show how to count the number of violations from the reduced Euler graph. We then define various transformations on the Euler graph which can reduce the number of violations of a given property, but sometimes at the expense of increasing the number of violations of another property. These transformations can be used to improve the quality of the drawn diagram, which is important for effective information visualization.

Area-proportional Venn diagrams are a popular way of visualizing the relationships between data sets, where the set intersections have a specified numerical value. In these diagrams, the areas of the regions are in proportion to the given values. Venn-3, the Venn diagram consisting of three intersecting curves, has been used in many applications, including marketing, ecology and medicine. Whilst circles are widely used to draw such diagrams, most area specifications cannot be drawn in this way and, so, should only be used where an approximate solution is acceptable. However, placing different restrictions on the shape of curves may result in usable diagrams that have an exact solution, that is, where the areas of the regions are exactly in proportion to the represented data. In this paper, we explore the use of convex shapes for drawing exact area proportional Venn-3 diagrams. Convex curves reduce the visual complexity of the diagram and, as most desirable shapes (such as circles, ovals and rectangles) are convex, the work described here may lead to further drawing methods with these shapes. We describe methods for constructing convex diagrams with polygons that have four or five sides and derive results concerning which area specifications can be drawn with them. This work improves the state-of-the-art by extending the set of area specifications that can be drawn in a convex manner. We also show how, when a specification cannot be drawn in a convex manner, a non-convex drawing can be generated.

Euler diagrams are a popular and intuitive visualization tool which are used in a wide variety of application areas, including biological and medical data analysis. As with other data visualization methods, such as graphs, bar charts, or pie charts, the automated generation of an Euler diagram from a suitable data set would be advantageous, removing the burden of manual data analysis and the subsequent task of drawing an appropriate diagram. To this end, various methods have emerged that automatically draw Euler diagrams from abstract descriptions of them. One such method draws some, but not all, abstract descriptions using only circles. We extend that method so that more abstract descriptions can be drawn with circles. Furthermore, we show how to transform any `undrawable' abstract description into a drawable one. Thus, given any abstract description, our method produces a drawing using only circles. The method has been implemented in a software tool available for download.

The use of haptic devices is becoming widespread, particularly with their growth in the home-games market and on mobile phones. Likewise, the number of haptic devices and APIs is increasing. However, it is still difficult to program and develop haptic applications. Consequently, there is a need to hide the complexity of programming a haptic application or interactions by providing prototyping tools or frameworks. In particular, one growing application area is haptic data visualization (also called haptification): the use of haptic devices to represent and realize information and data. This paper presents a visual prototyping tool for haptic interactions for data visualization. Users can easily and quickly create haptic interactions through a visual programming interface with tunable parameters. This paper also presents a user evaluation aimed at demonstrating that non-programmers can create simple haptic interactions and which also indicates potential improvements to the tool.

Euler diagrams are the only diagrams that intuitively represent containment, intersection and exclusion of data, but none of the current automatic diagram layout techniques produce good layouts in a reasonable time. We adopt a force-directed approach to automatically layout aesthetically pleasing Euler diagrams in a relatively fast time. A Java prototype demonstrates our novel force model.

Euler diagrams are the only diagrams that intuitively represent containment, intersection and exclusion of data, but none of the current automatic diagram layout techniques produce good layouts in a reasonable time. We adopt a force-directed approach to automatically layout aesthetically pleasing Euler diagrams in a relatively fast time. A Java prototype demonstrates our novel force model.

Haptic data visualization is a growing research area. It conveys information using the sense of touch which can help visually impaired people or be useful when other modalities are not available. However, as haptic devices and virtual worlds exhibit many challenges, the haptic interactions developed are often simple and limited to navigation tasks, preferring other modalities to relay detailed information. One of the principal challenges of navigation with haptic devices alone, particularly single point-based force-feedback devices, is that users do not know where to explore and thus obtaining an overview is difficult. Thus, this paper presents two types of interaction technique that aim to help the user get an overview of data: 1) a haptic scatter plot, which has not been investigated to any great degree, provided by a force model and 2) a new implementation for a haptic line chart technique provided using a guided tour model.

Euler diagrams form the basis of several visual modelling notations, including statecharts and constraint diagrams. Recently, various techniques for automated Euler diagram drawing have been proposed, contributing to the Euler diagram generation problem: given an abstract description, draw an Euler diagram with that description and which possesses certain properties. A common generation method is to find a dual graph from which an Euler diagram is subsequently created. In this paper we define transformations of the dual graph that allow us to alter the properties that the generated diagram possesses. In addition, because the dual graph of a previously generated diagram can be found, our transformations can be used to take such a diagram and produce a new diagram with the same abstract description, but with different properties. As a result, we can produce a variety of different diagrams for any given abstract description, allowing us to choose an Euler diagram that conforms to the properties that a user prefers.

Many data sets are visualized effectively with area proportional Venn diagrams, where the area of the regions is in proportion to a defined specification. In particular, Venn diagrams with three intersecting curves are considered useful for visualizing data in many applications, including bioscience, ecology and medicine. To ease the understanding of such diagrams, using restricted nice shapes for the curves is considered beneficial. Many research questions on the use of such diagrams are still open. For instance, a general solution to the question of when given area specifications can be represented by Venn3 using convex curves is still unknown. In this paper we study symmetric Venn3 drawn with convex curves and show that there is a symmetric area specification that cannot be represented with such a diagram. In addition, by using symmetric diagrams drawn with polygons, we show that, if area specifications are restricted so that the double intersection areas are no greater than the triple intersection area then the specification can be drawn with convex curves. We also propose a construction that allows the representation of some area specifications when the double intersection areas are greater than the triple intersection area. Finally, we present some open questions on the topic.

Euler diagrams are a natural method of representing set-theoretic data and have been employed in diverse areas such as Visualizing statistical data, as a basis for diagrammatic logics and for displaying the results of database search queries. For effective use of Euler diagrams in practical computer based applications, the generation of a diagram as a set of curves from an abstract description is necessary. Various practical methods for Euler diagram generation have been proposed, but in all of these methods the diagrams that can be produced are only for it restricted Subset of all possible abstract descriptions. We describe a method for Euler diagram generation, demonstrated by implemented software. and illustrate the advances in methodology via the production of diagrams which were difficult or impossible to draw using previous approaches. To allow the generation of all abstract descriptions we may be reqUired to have some properties of the final diagram that are not considered nice. In particular we permit more than two curves to pass though it single point, permit sonic curve segments to be drawn Concurrently, and permit duplication of curve labels. However, Our method attempts to minimize these bad properties according to it chosen prioritization.

Euler diagrams are widely used for information visualization and form the basis of a variety of formal languages that are used to express constraints in computing. Tools to automatically generate and layout these diagrams from an abstract description have to overcome the fact that this problem is computationally difficult. We develop a theory of isomorphism of diagram descriptions and identify invariants of these descriptions under isomorphism. We can apply this theory to improve the efficiency of the generation of all abstract descriptions (up to isomorphism). We can also consider the production and use of libraries of diagrams with nice visual properties: by providing a normal form for the abstract descriptions we can improve efficiency of searches for isomorphic diagrams within such libraries and, moreover, utilize invariants for further efficiency savings. We produce an implementation of the theory and give an indication of the efficiency improvements.

Euler diagrams have a wide variety of uses, from information visualization to logical reasoning. In all of their application areas, the ability to automatically layout Euler diagrams brings considerable benefits. In this paper, we present a novel approach to Euler diagram generation. We develop certain graphs associated with Euler diagrams in order to allow curves to be added by finding cycles in these graphs. This permits us to build Euler diagrams inductively, adding one curve at a time. Our technique is adaptable, allowing the easy specification, and enforcement, of sets of wellformednesss conditions; we present a series of results that identify properties of cycles that correspond to the wellformedness conditions. This improves upon other contributions towards the automated generation of Euler diagrams which implicitly assume some fixed set of wellformedness conditions must hold. In addition, unlike most of these other generation methods, our technique allows any abstract description to be drawn as an Euler diagram. To establish the utility of the approach, a prototype implementation has been developed.

Euler diagrams are collections of labelled closed curves. They are often used to represent information about the relationship between sets and, as such, they have numerous applications including: visualizing biological data, diagrammatic logics, and visual database querying. Various methods to automatically generate Euler diagrams have been proposed recently. Typically, the generation process starts with an abstract description of an Euler diagram, which is then converted to a planar dual graph. Finally, the process attempts to embed the Euler diagram from the dual graph. This paper describes a method for embedding wellformed Euler diagrams from dual graphs. There are several mechanisms to generate dual graphs but, prior to the novel work described here, no general method for embedding a wellformed Euler diagram from a dual graph had been demonstrated. The method in this paper achieves an embedding of any wellformed Euler diagram. The method first triangulates the dual graph. Then, using the faces of the triangulated graph, an edge labelling technique identifies the vertices of polygons which form the closed curves of the Euler diagram. The method is demonstrated by a Java implementation. In addition, this paper discusses a number of layout improvements that can be explored for this embedding method.

We describe an empirical investigation into layout criteria that can help with the comprehension of Euler diagrams. Euler diagrams are used to represent set inclusion in applications such as teaching set theory, database querying, software engineering, filing system organisation and bio-informatics. Research in automatically laying out Euler diagrams for use with these applications is at an early stage, and our work attempts to aid this research by informing layout designers about the importance of various Euler diagram aesthetic criteria. The three criteria under investigation were: contour jaggedness, zone area inequality and edge closeness. Subjects were asked to interpret diagrams with different combinations of levels for each of the criteria. Results for this investigation indicate that, within the parameters of the study, all three criteria are important for understanding Euler diagrams and we have a preliminary indication of the ordering of their importance.

We describe a system that enables us to perform exploratory empirical experiments with graph visualization techniques by incorporating them into games that can be played on an internet site, the Graph Games Website (http://www.cs.kent.ac.uk/projects/graphmotion/). We present a general discussion of games as a test-bed for empirical experiments in graph comprehension, and explain why they might, in particular, provide a useful way to do exploratory experiments. We then discuss the requirements for games that can be used and describe some individual games including those we have tried on our own site. The main part of the paper describes our own experiment in setting up a graph-gaming site where we have carried out tests on the benefits of different graph visualizations. We discuss the design of the site, describe its underlying architecture and present a promising initial trial on movement in graph visualization that gathered the results from over 70,000 played games. We then present some statistical conclusions that can be drawn from the resulting data. Finally, we summarize the lessons that have been learned and discuss ideas for future work.

This paper contains details of new criteria for graph layout, based on the concepts used in graphical design. Current graph layout criteria have been shown to be effective in measuring the quality of a graph layout, but they are ad-hoc and often miss subtle appearance considerations such as balance and distribution. We discuss how the principles concerning the layout of text and diagrams from design can be applied to graph layout and show how two new metrics can be implemented based on these criteria. We also give preliminary examples of layout generated using the new metrics.

In this paper, we describe a tool to improve inter-functional communication of project plans by displaying them as a metro map. Our tool automatically lays out plans using a multicriteria system adapted for the application area. Previous studies have shown that displaying project plans using a metro map metaphor as a complementary visualization to Gantt charts attracts and engages individuals, presents an overview of detail and initiates discussions. Creating such a map manually is time consuming. Hence, we have developed a software tool that converts a standard planning format into a metro map visualization and assists designers in generating comprehensible layouts. Our findings may be important for researchers in the domain of human computer interaction, project managers, knowledge visualization and communication scientists.

Diagrammatic notations, such as the Unified Modeling Language (UML), are in common use in software development. They allow many aspects of software systems to be described diagrammatically, but typically they rely on textual notations for logical constraints. In contrast, spider diagrams provide a visual notation for expressing a natural class of set- theoretic statements in a diagrammatic form. In this paper we present a tableau system for spider diagrams, and describe an implementation of the system. In a software development context, the system allows users to explore the implications of design choices, and thus to validate specifications; beyond this, the tableau algorithm and system are of general interest to visual reasoners.

We describe an empirical investigation into layout criteria that can help with the comprehension of Euler diagrams. Our work is intended to inform automatic Euler diagram layout research by confirming the importance of various Euler diagram aesthetic criteria. The three criteria under investigation were: smoothness, zone area equality and edge closeness. Subjects were asked to interpret diagrams with different combinations of levels for each of the criteria. Results for this investigation indicate that, within the parameters of the study, all three criteria are important for understanding Euler diagrams and we have a preliminary indication of the ordering of importance for the criteria.

A 3-Venn diagram is used to represent all possible combinations of three characteristics and is most commonly drawn with three overlapping congruent circles. In this paper, we investigate the conditions under which area-proportional circular 3-Venn diagrams exist, and for those untenable cases, we present an optimization strategy for approximating a solution. In the conclusion, we describe how these results can be extended to the case of 3-Euler diagrams.

We describe a computer-based system to automatically lay out metro maps using multicriteria optimization. The starting layout for the method is the geographic layout or a sketch of the map. The system attempts to improve this layout. It measures the map by calculating a number of criteria. These criteria are weighted and summed together: stations are moved if the sum of the weighted criteria is reduced. An iteration of the method consists of attempting to move each station in the map. There are several enhancements to the method: stations are placed on an grid, a clustering algorithm is used to find groups of stations that can be moved together, and labelling of stations is performed with a number of additional criteria. Example results using real-world metro maps look promising.

This paper compares the effectiveness of the Project Tube Map and the Gantt Chart for interfunctional communication in large projects where different stakeholders are involved. Today, Gantt Charts are well known in project management. However, the use of Gantt Charts has limitations: It fails in motivational aspects, it has difficulties to illustrate who is collaborating with whom, and it supports badly recall. The Project Tube Map has been introduced earlier as an approach to overcome these limitations. This paper compares the effectiveness of both visualization methods. Our findings from the evaluation of 44 interviews indicate that the Project Tube Map is more effective for (1) drawing attention and keeping interest, (2) presenting overview and detail, (3) visualizing who is collaborating with whom, (4) motivating people to participate in the project, and (5) increasing recall. The findings indicate that both formats complement each other. We further present an algorithm that allows the automatic creation of Project Tube Maps. The results presented in this paper are important for researchers and practitioners in the fields of Knowledge Visualization, Project Management, Visual Communication Sciences, and Information Visualization.

Modeling is a technique used extensively in industry to define software systems, the UML being the most prominent example. With the increased use of modeling techniques has come the desire to use model transformations. While the current OMG standards such as Unified Modeling Language (UML) and Meta Object Facility (MOF) provide a well-established foundation for defining models, no such well-established foundation exists for transforming models. The current paper describes how the OCL expressions are integrated in a transformation language called YATL (Yet Another Transformation Language) to provide support for model querying. The paper presents also the transformation environment and the main features of YATL.

In this paper we describe a method to lay out a graph enhanced Euler diagram so that it looks similar to a previously drawn graph enhanced Euler diagram. This task is non-trivial when the underlying structures of the diagrams differ. In particular, if a structural change is made to an existing drawn diagram, our work enables the presentation of the new diagram with minor disruption to the user's mental map. As the new diagram can be generated from an abstract representation, its initial embedding may be very different from that of the original. We have developed comparison measures for Euler diagrams, integrated into a multicriteria optimizer, and applied a force model for associated graphs that attempts to move nodes towards their positions in the original layout. To further enhance the usability of the system, the transition between diagrams can be animated.

We describe a system to automatically generate metro maps using a multicriteria approach. We have implemented a hill climbing optimizer which uses a fitness score generated from a sum of several aesthetic metrics. This is used to move from the initial geographic layout of the map to a schematic layout that is intended to aid travellers navigation. We describe the software and show its application to a number of real world metro maps.

We describe the results of empirical investigations that explore the effectiveness of moving graph diagrams to improve the comprehension of their structure. The investigations involved subjects playing a game that required understanding the structure of a number of graphs. The use of a game as the task was intended to motivate the exploration of the graph by the subjects. The results show that movement can be beneficial when there is node-node or node-edge occlusion in the graph diagram but can have a detrimental effect when there is no occlusion, particularly if the diagram is small. We believe the positive result should generalise to other graph exploration tasks, and that graph movement is likely be useful as an additional graph exploration tool.

We describe a method for drawing graph-enhanced Euler diagrams using a three stage method. The first stage is to lay out the underlying Euler diagram using a multicriteria optimizing system. The second stage is to find suitable locations for nodes in the zones of the Euler diagram using a force based method. The third stage is to minimize edge crossings and total edge length by swapping the location of nodes that are in the same zone with a multicriteria hill climbing method. We show a working version of the software that draws spider diagrams. Spider diagrams represent logical expressions by superimpos-ing graphs upon an Euler diagram. This application requires an extra step in the drawing process because the embedded graphs only convey information about the connectedness of nodes and so a spanning tree must be chosen for each maximally connected component. Similar notations to Euler diagrams enhanced with graphs are common in many applications and our method is generalizable to drawing Hypergraphs represented in the subset standard, or to drawing Hi-graphs where edges are restricted to connecting with only atomic nodes.

In this paper, we present a coordination model for exploratory multi-view visualization. We base our work on current research in exploratory visualization and other disciplines. Our model is based on sharing abstract objects such as the visualization parameters of the dataflow model to achieve coordinated exploratory tasks in multiple views. This model describes how current coordinations in exploratory visualization work and allows novel coordinations to be constructed.

This paper describes a graph visualization method that attempts to aid the understanding of graphs by adding continuous local movement to graph diagrams. The paper includes a discussion of some of the many different kinds of potential graph movement and then describes an empirical trial that was conducted to investigate whether one kind of movement helps with a particular graph comprehension task. Although the results of the trial are promising, the degree of benefit afforded by the movement varies between graphs and the paper includes a discussion about graph features which may account for this discrepancy.

This paper introduces a new edge length heuristic that finds a graph layout where the edge lengths are proportional to the weights on the graph edges. The heuristic can be used in combination with the spring embedder to produce a compromise between a drawing with an accurate presentation of edge length and a drawing with good general comprehensibility. We describe our preliminary investigations in combining the two methods so that a user can tune their preference and demonstrate the effectiveness of the system on both randomly generated graphs and graphs representing web page similarity data.

Most coordination realizations in current visualization systems are ''last-minute'' ad-hoc and rely on the richness of the chosen implementation language. Moreover, very few visualization models implicitly consider coordination. If coordination is contemplated from the design point of view, it is usually only regarded as part of the communication protocol and is generally dealt with within that restricted domain. Coordinated multiple views are beneficial and a flexible model for coordination will ensure easy embedding of coordination in such exploratory environments. This paper compares different approaches to coordination in exploratory visualization (EV). We recognize the need for a coordination model and for that we formalize aspects of coordination in EV. Furthermore, our work draws on the findings of the interdisciplinary study of coordination by various researchers.

We present an aesthetics based method for drawing Euler diagrams. Aesthetic layout metrics have been found to be useful in graph drawing algorithms, which use metrics motivated by aesthetic principles that aid user understanding of diagrams. We have taken a similar approach to Euler diagram drawing, and have defined a set of suitable metrics to be used within a hill climbing multicriteria optimiser to produce good drawings. There are added difficulties when drawing Euler diagrams as they are made up of contours whose structural properties of intersection and containment must be preserved under any layout improvements. In this paper we describe our Java implementation of a pair of hill climbing variants to find good drawings, a set of metrics that measure aesthetics for good diagram layout, and issues concerning the choice of weightings for a useful combination of the metrics.

Spring embedding is a widely used method for producing automated layouts of graphs. We present a preprocessor that improves the performance of the classical spring embedder which can be used in conjunction with other optimization and approximation techniques. It creates an initial graph layout with edge lengths that are approximately equal and with a minimum node separation from which the spring embedder typically needs far fewer iterations to produce a well laid out graph.

The process of normalisation has long been accepted as a crucial part of the design for good database systems. By using a declarative approach to the specification of the normalisation rules and a precisely defined transformation, over a meta-model of a database system design language, we can automate the normalisation process. A tool supporting the normalisation of database system designs can subsequently be developed providing an invaluable aid to the software system designer.

Searching for information on the web is hard; the user may not know what they are looking for, they may refine their search from information gathered by preliminary naive searches, and they may be looking for luminous sites that have many external links so that they can browse further. Information visualization can aid the user in many of these search related tasks. Certainly, the user is familiar with browsing and manipulating the search results through textual style interfaces, but they would gain a better understanding of the information through different presentation methods. Thus, we believe rank ordered lists should be used along-side abstract information visualization presentations. We present a system that displays multiple views of search result information. It provides views for displaying abstract visualization designs using multiform glyphs as well as a ranked text based list. Our engine also retrieves detailed information about the located sites (such as size of page, and quantities of internal and external links); and we describe two glyph designs that display this rich information.

We present a preprocessor for the spring embedder graph drawing method and show its use in speeding up the automatic layout of three-dimensional visualizations of WWW sites. Spring embedding is a widely used method for visualizing the connections in WWW maps, as it can typically produce a reasonable layout for most general graphs. However, the technique does not scale well and to improve the performance when dealing with large graphs various optimisations have been developed. Our preprocessor is a new optimization method that attempts to obtain a reasonably good initial drawing to be then used by the spring embedder. This initial drawing has edge lengths that are approximately equal along with a minimum node separation. This produces a layout that is closer to the final drawing than a random scattering of nodes and so allows fewer invocations of the spring embedder to produce an equally stable drawing.

An XML Specification for Grrr Programs Peter Rodgers Computing Laboratory University of Kent Given is an XML DTD and worked example to show how a Grrr program might be stored in a form that allows conversion to other graph transformation systems. Contribution to the University of Paderborn GT Exchange Formats Meeting. This is GRXL draft version 0.1.

Graph rewriting is becoming increasingly popular as a method for programming with graph based data structures. We present several modifications to a basic serial graph rewriting paradigm and discuss how they improve coding programs in the Grrr graph rewriting programming language. The constructs we present are once only nodes, attractor nodes and single match rewrites. We illustrate the operation of the constructs by example. The advantages of adding these new rewrite modifiers is to reduce the size of programs, improve the efficiency of execution and simplify the host graph undergoing rewriting.

This paper overviews the graph rewriting programming language, Grrr. The serial graph rewriting strategy is detailed, and key elements of the user interface are described. The system is illustrated by a simple example.

We discuss geometric positioning, highlighting of visited nodes and user defined highlighting that form the algorithm animation facilities in the Grrr graph rewriting programming language. The main purpose of animation was initially for the debugging and profiling of Grrr code, but recently it has been extended for the purpose of teaching algorithms to undergraduate students. The animation is restricted to graph based algorithms such as graph drawing, list manipulation or more traditional graph theory. The visual nature of the Grrr system allows much animation to be gained for free, with no extra user effort beyond the coding of the algorithm, but we also discuss user defined animations, where custom algorithm visualisations can be explicitly defined for teaching and demonstration purposes.

We present new pragmatic constructs for easing programming in visual graph rewriting programming languages. The first is a modification to the rewriting process for nodes the host graph, where nodes specified as 'Once Only' in the LHS of a rewrite match at most once with a corresponding node in the host graph. This reduces the previously common use of tags to indicate the progress of matching in the graph. The second modification controls the application of LHS graphs, where those specified as 'Single Match' are tested against the host graph one time only. This reduces the need for control flags to indicate the progress of execution of transformations.

This paper describes a hybrid Genetic Algorithm (GA) that is used to improve the layout of a graph according to a number of aesthetic criteria. The GA incorporates spatial and topological information by operating directly with a graph based representation. Initial results show this to be a promising technique for positioning graph nodes on a surface and may form the basis of a more general approach for problems involving multi-criteria spatial optimisation.

This paper describes Grrr, a prototype visual graph drawing tool. Previously there were no visual languages for programming graph drawing algorithms despite the inherently visual nature of the process. The languages which gave a diagrammatic view of graphs were not computationally complete and so could not be used to implement complex graph drawing algorithms. Hence current graph drawing tools are all text based. Recent developments in graph rewriting systems have produced computationally complete languages which give a visual view of graphs both whilst programming and during execution. Grrr, based on the Spider system, is a general purpose graph rewriting programming language which has now been extended in order to demonstrate the feasibility of visual graph drawing.

We describe GGI, a visual system that allows the user to execute an automatically generated data flow graph containing code modules that perform natural language processing tasks. These code modules operate on text documents. GGI has a suite of text visualisation tools that allows the user useful views of the annotation data that is produced by the modules in the executable graph. GGI forms part of the GATE natural language engineering system.

We describe a software environment to support research and development in natural language (NL) engineering. This environment -- GATE (General Architecture for Text Engineering) -- aims to advance research in the area of machine processing of natural languages by providing a software infrastructure on top of which heterogeneous NL component modules may be evaluated and refined individually or may be combined into larger application systems. Thus, GATE aims to support both researchers and developers working on component technologies (e.g. parsing, tagging, morphological analysis) and those working on developing end-user applications (e.g. information extraction, text summarisation, document generation, machine translation, and second language learning). GATE will promote reuse of component technology, permit specialisation and collaboration in large-scale projects, and allow for the comparison and evaluation of alternative technologies. The first release of GATE is now available.

Euler diagrams have been used for centuries as a means for conveying logical statements in a simple, intuitive way. They form the basis of many diagrammatic notations used to represent set-theoretic relationships in a wide range of contexts including software modelling, logical reasoning systems, statistical data representation, database search queries and file system management. In this paper we survey notations based on Euler diagrams with particular emphasis on formalization and the development of software tool support.

We describe an empirical investigation into some of the layout criteria that may facilitate the comprehension of Euler diagrams. The three criteria under investigation were: smoothness, zone area equality and edge closeness. Subjects were asked to interpret diagrams that had good and bad levels of each criterion. The goal of this research is an initial step into using empirical evidence to support decisions concerning the metrics used for automated layout of Euler diagrams. Results for this investigation indicate that, within the parameters of the study, all three criteria are important for understanding Euler diagrams and we have a preliminary indication of the ordering of importance for these criteria.

This book constitutes the refereed proceedings of the 7th International Conference on Theory and Application of Diagrams, Diagrams 2012, held in Canaterbury, UK, in July 2012. The 16 long papers, 6 short papers and 21 poster abstracts presented were carefully reviewed and selected from 83 submissions. The papers are organized in keynotes, tutorial, workshops, graduate student symposium and topical sections on psychological and cognitive issues, diagram layout, diagrams and data analysis, Venn and Euler diagrams, reasoning with diagrams, investigating aesthetics, applications of diagrams.