Automated Generation of Schematic Network Maps with Preservation of Main Structures

Abstract. Schematic (network) maps are helpful for people to perform route planning and orientation tasks. The London Underground Map designed by Harry Beck is an excellent example of such maps. Generally, there are three approaches to generate schematic maps: manual, semi-automated (or computer-aided) and fully automated. In the past twenty years, many researchers have been devoted to the development of automated methods for generation of schematic maps. In these automated methods, various sets of constraints are used. Most of these constraints are for geometric properties of individual features (such as the lengths and orientations of lines); a few constraints are for relations between features (such as the minimum distance threshold between non-incident edges); but none are explicitly for the main structures of whole networks. It is believed that preservation of the main structure is the most important, because main structure is represented by global features which is first recognized by a pre-attentive process in human cognition – a global-to-local process (in which local features are then recognized by an attentive process). It is hypothesized here that an automated method with the preservation of main structures of networks should be able to generate schematic maps with improved clarity and aesthetics.

This paper describes the development of an automated method with the preservation of the main structures of line networks. In this method, automated schematization is treated as an optimization problem and is represented as a Mixed-Integer Programming (MIP) model, which consists of an objective function and a set of constraints. The preservation of main structures is modelled into constraints (i.e., making important lines straight and orientating them to specific directions) for the model. The MIP model is imported into a commercial optimization software called “IBM ILOG CPLEX Optimization Studio” (version 12.6.3) for the acquisition of optimal solutions (i.e., coordinates of vertices and edges on schematic maps). The whole process is shown in Figure 1.

Experimental evaluations have been conducted with a set of real-life data as shown in Figure 2a and 2d. Schematic maps are generated by this new method with the preservation of main structures and by an old method without the particular consideration for main structures, as shown in Figures 2b, 2c, 2e and 2f. A psychological test with a questionnaire has been conducted, which consists of questions regarding “clarity”, “recognition of major lines”, “visual simplicity” and “satisfaction”. It is found that, in all these four aspects, the map generated by new methods with preservation of main structures have higher scores than those by the old method. These improvements are proved to be significant after paired-t tests.

Therefore, it is concluded that the new automated method with the preservation of main structures can generate schematic maps with significant improvement in clarity and aesthetics. This study is helpful to improve automated methods for generation of schematic maps and other visual representations.