Skip to main content
Kent Academic Repository

Improving Automated Layout Techniques for the Production of Schematic Diagrams

Chivers, Daniel (2014) Improving Automated Layout Techniques for the Production of Schematic Diagrams. Doctor of Philosophy (PhD) thesis, University of Kent,. (KAR id:50750)

Language: English
Download this file
[thumbnail of 6Thesis_DanChivers.pdf]


This thesis explores techniques for the automated production of schematic diagrams, in particular those in the style of metro maps. Metro map style schematics are used across the world, typically to depict public transport networks, and therefore benefit from an innate level of user familiarity not found with most other data visualisation styles. Currently, this style of schematic is used infrequently due to the difficulties involved with creating an effective layout – there are no software tools to aid with the positioning of nodes and other features, resulting in schematics being produced by hand at great expense of time and effort.

Automated schematic layout has been an active area of research for the past decade, and part of our work extends upon an effective current technique – multi-criteria hill climbing. We have implemented additional layout criteria and clustering techniques, as well as performance optimisations to improve the final results. Additionally, we ran a series of layouts whilst varying algorithm parameters in an attempt to identify patterns specific to map characteristics. This layout algorithm has been implemented into a custom-written piece of software running on the Android operating system. The software is targeted at tablet devices, using their touch-sensitive screens with a gesture recognition system to allow users to construct complex schematics using sequences of simple gestures.

Following on from this, we present our work on a modified force-directed layout method capable of producing fast, high-quality, angular schematic layouts. Our method produces superior results to the previous octilinear force-directed layout method, and is capable of producing results comparable to many of the much slower current approaches. Using our force-directed layout method we then implemented a novel mental map preservation technique which aims to preserve node proximity relations during optimisation; we believe this approach provides a number of benefits over the the more common method of preserving absolute node positions. Finally, we performed a user study on our method to test the effect of varying levels of mental map preservation on diagram comprehension.

Item Type: Thesis (Doctor of Philosophy (PhD))
Thesis advisor: Rodgers, Peter
Uncontrolled keywords: Graphs Metro Map Automated Layout Force-directed Hill-climbing
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Users 1 not found.
Date Deposited: 02 Oct 2015 11:00 UTC
Last Modified: 13 Dec 2022 07:41 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Chivers, Daniel.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.