Aspect-Ratio-Preserved Labeling on Metro Maps
Hsiang-Yun Wu

Ken Maruyama

Takamasa Kawagoe

Kazuo Misue

TU Wien, Austria
hsiang.yun.wu@acm.org

University of Aizu, Japanx.mt.maru@gmail.com

University of Aizu, Japan
m5211138@u-aizu.ac.jp

University of Tsukuba, Japanmisue@cs.tsukuba.ac.jp

Masatoshi Arikawa

Shigeo Takahashi

Akita University, Japanarikawa@ie.akita-u.ac.jp

University of Aizu, Japan
takahashis@acm.org

Abstract—For better readability, metro lines are often alignedalong the octilinear directions. Predeﬁned layouts, however, limit
the feasibility of placing station name labels. In this paper, wepresent a novel approach to automating the placement of station
names around a schematic network while maximally respecting
its original layout as the mental map. The idea behind the
proposed approach is to progressively annotate stations fromcongested central downtown areas to sparse rural areas by introducing the sum of geodesic distances over the network to identify
the proper order of stations to be annotated. Our approach
elongates line segments of the network without changing theirdirections to spare labeling space around the station. Additional
constraints are introduced to restrict the aspect ratios of theregion conﬁned by the metro network for better preservation ofthe mental map in the original schematic layout.
Index Terms—Progressive Annotation, Geodesic Distances,
Schematic Layouts, Mental Maps, Mixed-Integer Programming

I. I NTRODUCTION
Metro maps serve as the common media for travelers to explore the transportation networks of the metro lines available inmajor cities. Such maps are often transformed into schematic
diagrams for better readability of the network topology. In
particular, octilinear layouts are the most common form. The
are obtained by aligning metro line segments to horizontal,vertical, and 45-degree slanting directions. This representation
originates from the design criteria invented by Henry Beck [1].
Properly placing stations on schematic metro maps is also
important, while this usually incurs additional technical challenges. This is primarily because the central downtown areaof such a schematic map is usually congested with multiple
metro lines around the interchange stations and thus it is
difﬁcult to ﬁnd enough space for labeling station names, whencompared with sparse rural areas around the terminals of themetro lines. This labeling problem becomes involved if thealignment of the name labels around the corresponding stationis restricted to one of the octilinear directions. Nöllenburg andWolff enable to automatically schematize geographical layoutsof metro networks in a visually plausible fashion [3], while
the technique still takes approximately 10 hours to compute
optimal label placement [3] for a middle sized network suchas Vienna metro network (Figure 1).
This paper presents a progressive approach for automaticallyannotating stations with their names while maximally respect-

Copyright of this manuscript is retained by the authors

ing the original layout of the schematic metro map. This isaccomplished by extending the authors’ previous work [4]for placing station names as labels progressively from thecrowded downtown area to sparse rural areas. Speciﬁcally, the
new approach imposes additional constraints that restrict thevariation in the aspect ratio of the regions conﬁned by themetro network, which allows to maximally retain the mental
map of the original schematic map.
II. M ETHODOLOGY
The proposed algorithm employs a mixed-integer programming (MIP) approach [3] to solve the constrained optimization
problems for schematizing the metro networks by minimizing
three different types of costs, which are line bends, relative
positions, and edge length. Once the metro network has
successfully been schematized, the next step is to place astation name label in the neighborhood of each station vertex.
A. Sorting station vertices for progressive annotation
The idea is to progressively place annotation labels one by
one from the crowded downtown area to sparse rural areas
around the boundary of the map domain. In this approach, thisidea is implemented by sorting the station vertices according
to the sum of geodesic (i.e., shortest topological) distances
within the metro network. In most cases, the aforementioned
approach can successfully place station names as annotation
labels while maintaining the mental map of the originalschematic layout. Nonetheless, the approach still fails to
sufﬁciently retain the mental map through the progressive annotation (see Figure 1(b)) because no constraints are explicitly
imposed to control the overall design of the metro map.
B. Extracting closed regions and preserving their aspect ratio
We found out that this problem is caused by the progressive
annotation technique not adequately retaining the original
aspect ratio of the speciﬁc features in the schematic metro
map. This inspires us to focus on the regions surrounded by themetro network in the downtown area, because the downtown
area is usually crowded with metro lines and interchange
stations and thus is more likely to contain feature regions
conﬁned by the metro lines. If the proposed approach canlimit the change in the aspect ratios of such feature regions,

1

(a)

(b)

(c)(d)

Fig. 1. Annotating the Vienna metro network. (a) Original schematic map. (b) A progressively annotated map without any constraints on the entire shape.
Progressively annotated maps while the aspect ratios of closed regions are constrained by the new constraints, where the tolerance error ratio E is set to be(c) E = 0.5 and (d) E = 0.1.

it can successfully mitigate the distortion of the user’s mental
map [2] of the metro map by constraining the changes oflayout geometry.
Let us denote w and h the width and height of a rectangle
respectively that tightly encloses the closed region. Thesevariables can naturally be derived from the upper and lower
limits of the closed region along the x- and y-axes as w =xmax − xmin and h = ymax − ymin .
Assume that the constant values W and H represents thewidth and height of a rectangle deﬁning the original closed
region just after the network schematization, respectively.
Since the aspect ratio of the closed region w
h should be kept
close to the original aspect ratio W,thefollowinginequality
HW
conditions are introduced as new constraints: (1+E)H≤wh ≤(1+E)W,H

original schematic layout of the synthesized metro map withthe three annotated versions and to select the best match forpreserving the mental map of the original schematic layout.
In these cases in which the simple progressive annotation cansuccessfully annotate stations of the schematic map without
excessively distorting the original layout, the participants
were likely to answer randomly, and the votes are uniformly
distributed over the three layouts. The participants did notdiscriminate between the constrained version with different
error tolerance ratios for the metro maps in Lisbon andVienna. This is probably because the difference between thetwo versions is small and the severe constraints sometimes
enlarge the closed regions a little excessively to meet the givenconditions.

where E is a constant that represents the error
tolerance ratio. These conditions can be rewritten as W h ≤(1+E)Hw and Hw ≤ (1+E)W h. It is clear that the aspectratio of the closed region w
h changes more signiﬁcantly if thecorresponding error tolerance ratio E increases. Thus, our new
formulation allows us to control the degree of distortion in the
progressive annotation process by adjusting the error tolerance
ratio E.

This paper reﬁnes an approach to progressively annotating
stations in schematic metro maps. The algorithm extracts
all closed faces conﬁned by the network and imposes the
proposed constraints on them to limit the variation in theiraspect ratio. More careful selection of such feature regions
may further improve the capability to maintain the underlying
mental map embedded in the original schematic layout.

III. R ESULTS

ACKNOWLEDGMENT

Our system has been implemented on a laptop PC with 3.1
GHz 6-Core Intel Core i5 CPU and 16GB RAM. Figure 1
presents the Vienna metro map, in which the network layout
in the central downtown area is strongly distorted. This undesirable deformation can be controlled with the help of theconstraints that preserves the aspect ratios of the closed regions
conﬁned by the network. The running time of each image isdepicted in Table I.

This work has been partially supported by JSPS KAKENHI(grant numbers 16H02825, 26730061, and 15K12032). Thiswork has also been conducted under the support by Joint
Research Program No. 398 at CSIS, the University of Tokyo.

TABLE IC OMPUTATION TIMES OF F IGURE 1 ( IN SECONDS ).
CityVienna

Figure 1(a)2.08

Figure 1(b)140.8

Figure 1(c)164.3

Figure 1(d)235.5

We also recruited 10 undergraduate and graduate students
to evaluate our approach. They were requested to compare theIV. C ONCLUSION AND F UTURE R ESEARCH D IRECTIONR EFERENCES[1] K. Garland. Mr. Beck’s Underground Map: A History. Capital Transport,
1994.
[2] K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and themental map. Journal of Visual Languages and Computing, 6(2):183–210,1995.
[3] M. Nöllenburg and A. Wolff. Drawing and labeling high-quality metro
maps by mixed-integer programming. IEEE Transactions on Visualization
and Computer Graphics, 17(5):626–641, 2011.
[4] Y. Yoshida, K. Maruyama, T. Kawagoe, H.-Y. Wu, M. Arikawa, andS. Takahashi. Progressive annotation of schematic railway maps. In
Proceedings of the 22nd International Conf. Information Visualization(IV2018), pages 373–378, 2018.

2