Automatic Diagram Generation

Lead Research Organisation: University of Brighton
Department Name: Sch of Computing, Engineering & Maths

Abstract

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.

Planned Impact

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.

Publications

10 25 50
publication icon
Bottoni P (2013) Spider Graphs: a graph transformation system for spider diagrams in Software & Systems Modeling

publication icon
Cordasco G (2017) Online region computations for Euler diagrams with relaxed drawing conventions in Journal of Visual Languages & Computing

publication icon
Fish A (2014) Equivalences in Euler-based diagram systems through normal forms in LMS Journal of Computation and Mathematics

 
Description We have provided a unified means of encoding diagrams from computer science for representing sets and their relationships, diagrams from mathematics for knots, with the methodology utilizing graphs and graph drawing techniques. This provides an understanding of the commonalities across different research areas. The use of this encoding within a diagram generation setting is powerful, enhancing state of the art capabilities, and the realization of the theory as a software tool provides great potential for future utility leading to non-academic impact.
Exploitation Route Further development of the software tool permitting integrated graph generation and interaction techniques will broaden its applicability, making it suitable for social networking and other application areas, of interest to industry as well as for use as an exploratory research tool.
Sectors Digital/Communication/Information Technologies (including Software),Education

 
Description Theory developed was used in production of software tool, which is being used as an exploratory research tool in areas of mathematics and computer science.
First Year Of Impact 2014
Sector Digital/Communication/Information Technologies (including Software)
 
Description Collaboration between the University of Brighton and La Sapienza, Rome. 
Organisation Sapienza University of Rome
Country Italy 
Sector Academic/University 
PI Contribution The project further developed the collaboration between the University of Brighton and La Sapienza, Rome, moving the collaboration into the area of diagram generation via the ADIGE project. Our research team leads the direction of the avenue of research on this project.
Collaborator Contribution They provided input into the theory relating of diagram encodings in the context of the ADIGE project. In general, they provide expertise in various areas including that of graph transformations.
Impact Paolo Bottoni, Andrew Fish, Alexander Heußner: Coloured Modelling Spider Diagrams. Diagrams 2014: 45-47 Paolo Bottoni, Andrew Fish and Francesco Parisi-Presicce. Spider Graphs: a graph transformation system for Spider diagrams. Journal of Software and Systems Modelling, 2013. Paolo Bottoni, Andrew Fish: Extending Spider Diagrams for policy definition. J. Vis. Lang. Comput. 24(3): 169-191 (2013) Paolo Bottoni, Gennaro Costagliola, Mattia De Rosa, Andrew Fish, Vittorio Fuccella: Euler diagram codes: interpretation and generation. VINCI 2013: 105-106 Paolo Bottoni, Andrew Fish: Policy enforcement and verification with Timed Modeling Spider Diagrams. VL/HCC 2013: 27-34 Paolo Bottoni, Gennaro Costagliola, Andrew Fish: Euler Diagram Encodings. Diagrams 2012: 148-162 Paolo Bottoni, Andrew Fish, Francesco Parisi-Presicce: Incremental update of constraint-compliant policy rules. ECEASST 39 (2011) Paolo Bottoni, Andrew Fish: A visual language for temporal specifications based on Spider diagrams. ECEASST 41 (2011) Paolo Bottoni, Gennaro Cordasco, Rosario De Chiara, Andrew Fish, Vittorio Scarano: Personalised Resource Categorisation Using Euler Diagrams. IS-EUD 2011: 251-257 Paolo Bottoni, Andrew Fish: Policy specifications with Timed Spider Diagrams. VL/HCC 2011: 95-98 Paolo Bottoni, Andrew Fish, Francesco Parisi-Presicce: Preserving constraints in horizontal model transformations. ECEASST 29 (2010) Paolo Bottoni, Andrew Fish: Coloured Euler Diagrams: A Tool for Visualizing Dynamic Systems and Structured Information. Diagrams 2010: 39-53
Start Year 2008
 
Description Collaboration between the University of Brighton and the University of Salerno, Italy 
Organisation University of Salento
Country Italy 
Sector Academic/University 
PI Contribution The published outcomes, and the software tool, have involved collaboration between academics and research students at the Universities of Brighton and Salerno. The PI and the RA visited the University of Salerno for collaborative meetings during the grant. We provide the main thrust of the theoretical input, and we are collaboratively working on developing the tools that realize the theory within the project.
Collaborator Contribution Whilst the ongoing software tool development is a collaborative effort across research teams, this partner substantially contributed via taking the primary role in the development of the front-end of the user interface for diagram sketching.
Impact Software tool: EulerSkech is java based software application for the drawing, generation and interaction with diagrams. Publications: Paolo Bottoni, Gennaro Costagliola, Mattia De Rosa, Andrew Fish, Vittorio Fuccella: Euler diagram codes: interpretation and generation. VINCI 2013: 105-106 Gennaro Costagliola, Mattia De Rosa, Andrew Fish, Vittorio Fuccella, Rafiq Saleh: Curve-based diagram specification and construction. VL/HCC 2013: 39-42 Paolo Bottoni, Gennaro Costagliola, Andrew Fish: Euler Diagram Encodings. Diagrams 2012: 148-162
Start Year 2012
 
Title Diagram Encoding and Generation tool 
Description The software tool, initially called EulerSketch, is an implementation permitting interactions with diagrams, such as: diagram sketching, editing, encoding and abstraction computations, and generation from an encoding. The software realizes theoretical algorithms developed as part of the project, utilizing and adapting theory and algorithms from the fields of knot theory and graph drawing. The software is freely available for download, via links at the project website: http://www.brighton.ac.uk/cem/research/adige/ . The research and the software development are ongoing, and the software will be periodically updated as new advances are made. 
Type Of Technology Software 
Year Produced 2013 
Open Source License? Yes  
Impact The software is still under development, but we have received a request for additional knot theoretic features as an aid as a research exploration tool. 
URL http://www.brighton.ac.uk/cem/research/adige/
 
Title EulerSketch software 
Description An updated version of the software tool, which has facilities for the construction, generation, and manipulation of curves based diagrams (e.g. Euler diagrams and knot diagrams). The tool incorporates underlying theory and algorithms that was developed within the project. 
Type Of Technology Software 
Year Produced 2017 
Open Source License? Yes  
Impact Notable impacts are yet to be demonstrated. 
URL https://github.com/cluelab/eulersketch
 
Description Delivery of lecture course at the European Summer School in Logic, Language and Information 2013 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact The PI delivered a course (entitled Why diagrammatic proofs are sometimes worth 1000 formulae: an Introduction to Formal Diagrammatic Reasoning Systems) at the 25th European Summer School in Logic, Language and Information (ESSLLI 2013), held at Heinrich Heine University in Dusseldorf, Germany, was presented between 5-9th August 2013. The course was delivered jointly with Alexander Huessner of the University of Bamberg, and audience of postgraduate students and academics from a range of areas (e.g. computer science, logic, linguistics, philosophy). The ADIGE project work and research directions were discussed within the course.

Discussions with various students occurred, in relation to their current or future research topics.
Year(s) Of Engagement Activity 2013
 
Description Seminar at Poste Italiane, Napoli, Italy. 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact A seminar was presented on Region-based diagrams: applications and automatic generation at Poste Italiane, Napoli, Italy, on 19th June 2013. Discussion occurred relating to the topic and the potential for usage in the industrial setting.

Discussion indicated good potential for desire for future use of tools within the industrial context, in the longer term, after substantial theory and tool developments, beyond the initial scope of the project.
Year(s) Of Engagement Activity 2013
 
Description Seminar at the Mathematics Department, University of Sussex, UK 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach Local
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Seminar on Representing and Generating Curve-based Diagrams at the Mathematics Department, University of Sussex, UK on 17th October 2013.

Discussions ensued at the Mathematics-Computer Science Interface.
Year(s) Of Engagement Activity 2013
 
Description Seminar at the University of Salerno, Italy. 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact Extended visit, including extensive discussions and seminar on Region-based diagrams: applications and automatic generation at the University of Salerno, Italy, on 24th June 2013.

Discussions related to the topic partly inspired a PhD student from Salerno, who was not working directly on the project, to visit the PI in the UK for several months in 2014.
Year(s) Of Engagement Activity 2013
 
Description Visist and Seminar at Monash University, Melbourne, Australia. 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact During a visit to Monash University, Melbourne, Australia, the project was discussed and a seminar presented on Automatic Diagram Generation on February 6, 2013. Discussions about the topic and the possible usage of the research group's theory and tools within the context of the project occurred.

The use of the team's work from Monash to significantly enhance the presentation of the output from the project's tool is actively under investigation.
Year(s) Of Engagement Activity 2013
 
Description Visit to Swinburne Centre for Comptuing and Engineering Software Systems, Melbourne, Australia, 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other academic audiences (collaborators, peers etc.)
Results and Impact A seminar was presented at Swinburne Centre for Computing and Engineering Software Systems, Melbourne, Australia, on Automatic Diagram Generation on February 13, 2013, and subsequent discussions occurred.



Seminar at Swinburne Centre for Comptuing and Engineering Software Systems, Melbourne, Australia, reporting on the project results, followed by discussions.

N/A
Year(s) Of Engagement Activity 2013