Skip to main content
Kent Academic Repository

Octilinear Force-Directed Layout with Mental Map Preservation for Schematic Diagrams

Chivers, Daniel, Rodgers, Peter (2014) Octilinear Force-Directed Layout with Mental Map Preservation for Schematic Diagrams. In: Diagrammatic Representation and Inference: 5th International Conference, Diagrams 2008, Herrsching, Germany, September 19-21, 2008. Proceedings of 8th International Conference, Diagrams 2014, Melbourne, VIC, Australia, July 28 - August 1, 2014. Lecture Notes in Computer Science . pp. 1-8. Springer, Berlin, Germany ISBN 978-3-662-44042-1. E-ISBN 978-3-662-44043-8. (doi:10.1007/978-3-662-44043-8_1) (KAR id:41428)


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.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1007/978-3-662-44043-8_1
Uncontrolled keywords: Force Directed, Schematic Layout, Delaunay Triangulation, Mental Map Preservation
Subjects: Q Science > QA Mathematics (inc Computing science)
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Peter Rodgers
Date Deposited: 15 Jun 2014 06:30 UTC
Last Modified: 09 Dec 2022 00:39 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:

Rodgers, Peter.

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.