Automatic Diagram Generation

Diagrams are an effective means of conveying a wide variety of different sources of information. The automatic generation of diagrams is essential for tasks such as the presentation of multiple views of large scale data sets (e.g. ontology analysis benefits from viewing information revolving around particular relationships). Enabling multiple significant relationships to be clearly presented greatly enhances the utility of visualisations (e.g. consider social network information presented as a diagram with graph edges used to depict the friends' relationship and containing curves to simultaneously indicate overlapping interest groups). The project aims to develop a unified framework for automatic diagram generation, allowing a mixture of features from different diagram types and enhancing control over layout; these theoretical advances are an essential precursor to use in practice. The project will provide significant academic impact (advances in the field, plus interaction between researchers in distinct fields) and industrial impact (improved support for ontology analysts, thereby reducing costs of product development cycles), and societal impact (enhanced communication between researchers and the public via improved visualisation capabilities). The involvement of prominent academic advisors from related fields and the substantial commitment from project partner Nokia will help to ensure the success of the project and assist in achieving long term impact.

A major problem is the Generation Problem (GP): given an abstract specification, decide if there is a suitable drawing satisfying the specification and if so, then to automatically produce one. The drawing conventions (constraints on the diagram syntax that must be satisfied) and drawing rules (constraints that are desirable to be satisfied) may vary according to application domain requirements or user preferences. There is a substantial amount of work on the graph-based GP, and the GP for the region-based Euler diagrams has recently been addressed, but there is a serious gap concerning diagrams that intrinsically contain both graph and region based features. Generation techniques for such mixed diagram types are desirable to enhance views of complex information (thereby assisting analysts) by enabling the visualisation of the grouping of items for emphasis, alongside a graph based visualisation of other ontological relationships. Other application areas include visual languages (e.g. diagrammatic logic proof presentation), information visualisation (e.g. geographic information systems, network visualisation), graph drawing and knot theory. Thus use of knot theoretic codes within the Euler diagram setting to enhance generation and layout techniques is a novel approach, taken in conjunction with a graph based generation methodology.

The automatic generation of diagrams has considerable potential for use as a means of efficiently and effectively displaying results or data in multiple scientific fields. Providing a single, formal basis will make the generation of diagrams easily accessible to researchers, without the need to reinvent techniques developed in other application areas. In general, communication between different disciplines is often difficult due to subject-specific terminologies and therefore research risks repetition. The development of a framework for automatically generating diagrams, which is applicable in different research areas, is important because it has the potential to stimulate communication and collaboration in different disciplines, as well as between researchers and industrial collaborators, by providing a common language. We will provide the theoretical grounding for software tools, enhancing industrial applicability as well as dissemination possibilities to the wider public and within the scientific community. The long term vision is that the project will set the groundwork for the establishment of a new field of Diagram Generation.

The proposed research will have a significant range of impacts with benefits to academic research, industry,
and education in society, and we indicate potential industrial and then societal impacts and vehicles to ensure their realisation.

Nokia are interested in the outcomes of this current project, have offered significant support and will help to ensure the research outcomes are utilised effectively. Their interest is due to the potential importance of the work to the visualisation of populated ontologies, requiring the generation of mixed region-graph based diagrams. Together we will explore case studies provided by Nokia, ensuring that the models and techniques developed are sufficient for their needs, whilst also indicating requirements for future extensions of the framework (e.g. for automated reasoning processes presentable via the presentation of sequences of diagrams). Plans will be developed with Nokia for the integration of the project results with complementary research projects, and for the construction of a larger scale follow-up project building on the theoretical basis that will be established. This will involve the creation of a software environment that realises the theoretical advances, enabling the generation of mixed-type diagrams, together with a scheme of experimental testing of the environment on users working in various domains (including analysts at Nokia). In the long term, the utilisation of the project results should improve support for analysts, thereby reducing the cost of product development cycles. The development of a single environment that can be utilised for multiple mixed diagram type interaction, rather than the development and use of multiple domain specific tools will save time and money in both development and time to learn, thereby providing substantial economic benefits.

There is further long term potential for industrial impact in the use of diagrammatic logics in software specification. The groundwork for this area was developed in the EPSRC funded project "Reasoning With Diagrams", focussing on Constraint Diagrams as a potential diagrammatic replacement for the existing textual constraint language within the diagrammatic modelling paradigm of the standard Unified Modeling Language. To encourage industrial uptake in this area, software tools to automatically generate and manipulate diagrams are essential, and the EPRSC funded project "Visualisation with Euler Diagrams" has provided grounds for the automatic generation of the Euler diagrams and the extension to mixed region-graph based diagrams will be a substantial step towards the development of practical tools.

In terms of impact on the project team, the project will be highly significant. It will provide the Research Assistant with experience of working in a research project environment, and collaboration with leading academics in multiple fields and well as with industrial partners. This is a tremendous opportunity for a researcher to develop an extensive network of contacts crossing both academic disciplines and industrial boundaries. As such, the position will likely be very desirable, and with the assistance of the project partners, a talented researcher is likely to take up the role, leading to a greater chance of outstanding results from the project. The principal investigator will also gain valuable experience of research project management, enhancing the chances of a successful research career by providing him with an opportunity to become established as a prominent figure in the field.

We will organise outreach events at schools, offering recreational mathematics talks and a general seminar about research in academia and industry with the aim of enhancing their knowledge, appreciation, and interest in research, showcasing the Automatic Diagram Generation project as an exemplar; the visualisation aspect makes the project particularly well suited to being made accessible to a younger audience.