An Algorithm for Accurate and Simple-Looking Metaphorical Maps

The known techniques either build complex metaphorical maps with perfect cartographic accuracy [2, 16, 24] or simple-looking metaphorical maps with cartographic error up to 30% [17]. In this work, we address this gap and aim towards producing simple metaphorical maps with near zero cartographical error.

• $\mathrm{■}$

  We present a multi-fold extension of the algorithm in [17]. More specifically:

  • –

    Towards improving accuracy: We introduce the notion of region stiffness and suggest a technique for varying the stiffness based on the current pressure of map regions.

  • –

    Towards maintaining simplicity: We introduce a weight coefficient to the pressure force exerted on each polygon point based on whether the corresponding point appears along a narrow passage.

  • –

    Towards generality: We cover, in contrast to [17], non-triangulated graphs. This is done by either generating points where more than three regions meet or by introducing holes in the metaphorical map.

• $\mathrm{■}$

  We perform an extended experimental evaluation which aims to:

  • –

    Compare our algorithm to the algorithm of Mchedlidze and Schnorr [17] with respect to cartographic accuracy and complexity.

  • –

    Examine the cartographic accuracy vs the regions’ complexity trade-off.

  • –

    Evaluate the extension to non-triangulated graphs.

  • –

    Evaluate the influence of the initial layouts on the quality of the maps, by comparing the initial layout as suggested in [17] to the cartographically accurate initial layout given by the theoretical approach in [3].

• $\mathrm{■}$

  Our experiments among other facts indicate that the suggested algorithm achieves almost perfect cartographic accuracy with only a small increase in polygon complexity compared to [17].

In Section 2, we present our notation, the quality metrics employed in evaluating cartographic maps as well as the basic ingredients of the algorithm of Mchedlidze and Schnorr [17]. In Section 3, we present our algorithm which (a) introduces the notion of region stiffness, (b) applies corrective weight coefficients on pressure forces, and (c) handles non-triangulated plane graphs. Our experimental evaluation is presented in Section 4. Finally, we conclude in Section 5 with directions for future work.

A demo application for generating metaphorical maps has been implemented in JavaScript using yFiles [28] and is available as a web application at http://aarg.math.ntua.gr/demos/metaphoric_maps/. All experiments were executed using a Java implementation. To allow replicability, we make the implementation and the whole graph benchmark publicly available at https://github.com/ekatsanou/metaphorical-maps.

After examining the output of the MS-algorithm, we observed that some regions had noticeably higher cartographic error than others, leading to the conclusion that some attributes of a region made it less responding to air pressure and, thus, resulted in high cartographic errors. Therefore, for every region we introduce a variable, which we refer to it as stiffness coefficient, that accounts for its stiffness. Let $g$ be an internal region and let $P_i(g)$ be its pressure at the $i$-th iteration of the force-directed algorithm. If at iteration $i$ region $g$ is over-pressured (i.e., $P_i(g)>1$) we increase the region’s stiffness coefficient by a small amount $step$; if it is under-pressured (i.e., ) we decrease it by $step$, otherwise, it remains unchanged. In addition, we restrict the stiffness coefficient in the range $[s_{\text{low}},s_{\text{high}}]$ where $s_{\text{high}}\ge 1$ and $s_{\text{low}}=\frac{1}{s_{\text{high}}}$. An appropriate value for $s_{\text{high}}$ is determined experimentally.

Given a region $g$, we define the stiffness coefficient of $g$ at the $i$-th iteration of the algorithm, denoted by $s_i(g)$, as:

where

Then, the revised air-pressure force of region $g$ on its boundary edge $e$ during the $i$-th iteration of the algorithm, $i\ge 1$, denoted by ${𝐅}_{𝐢}^{\prime }(e,g)$ is defined as

where ${𝐅}_{𝐢}(e,g)$ is the air-pressure force computed at the $i$-th iteration of the MS-algorithm. Note that the “stiffness” attribute is different for each region and demonstrates an adaptive behaviour over time. Employing such adaptive coefficients in force/energy-directed drawing algorithms appears to be uncommon, mainly due to performance issues. However, we note that a similar scheme has been employed in the work of Hu [14] (referred to as adaptive cooling scheme).

We performed a few experiments (see [15] for details) with 20-node graphs in order to determine the parameters of the algorithm, that resulted in the following values: $\text{step}=0.02$, $\text{iter}=1.000$ and $s_{\text{high}}=8$. To also account for the size of the input graph, assuming that larger graphs take a longer time to converge to a good metaphorical map, we decided to set the number of iterations to $\text{iter}=800+10n$, the value consistent with $\text{iter}=1.000$ for $n=20$.

When we applied the stiffness coefficients to the regions, we observed that they tended to create long, narrow passages, thereby reducing the visual complexity of the metaphorical map. To mitigate this effect, we introduce a new corrective weight coefficient for the pressure forces exerted on each region’s vertices, while keeping the total pressure of the region constant. These weight coefficients redistribute pressure so that vertices in narrow passages receive a larger share of the force, whereas vertices in wider parts of the region receive less. Before defining the weight coefficient, we introduce some auxiliary notation:

• $\mathrm{■}$

  Let $M$ be a metaphorical map, and let $\rho (M)=\sqrt{\left(\sum _{g\in M}A(g)\right)/\pi }$ denote the radius of a circle whose area equals the total area of $M$. We refer to $\rho (M)$ as the ideal radius of $M$.

• $\mathrm{■}$

  Let $g$ be a region of $M$, let $u$ be one of its vertices and let $e$ be an edge of $g$ that is not adjacent to $u$. Further, let $x$ be the point of $e$ that is closest to $u$. The Euclidean distance of $u$ to $e$, denoted by $d_E(u,e)$, is simply the Euclidean distance from $u$ to point $x$. We also define the polygonal distance of vertex $u$ to edge $e$, denoted by $d_P(u,e)$, as the length of the shortest path when moving from $u$ to $x$ on the boundary of $g$.

Intuitively, an edge $e$ is sufficiently “opposite” to a vertex $u$ if it is close to it and, at the same time, it belongs to the opposite side of a narrow passage. For each vertex $u$ of region $g$, we want to identify the edge $e$ of $g$ that is the closest out of those opposite to it. In order to avoid selecting edges that are collinear with $u$, we consider only edges for which it holds that and, out of those, we select the edge $e$ of smallest Euclidean distance to $u$. We refer to this edge $e$ as the pairing edge of $u$ and we denote it by $pair(u)$. Further, we denote the Euclidean distance from $u$ to $pair(u)$ by $d(u,g)$.

Consider the metaphorical map $M$. We introduce a scale factor based on the ideal radius $\rho (M)$. We regard $0.05\rho (M)$ as the minimum “acceptable” passage width and, hence, we define the quantity $\delta (u,g)=\frac{0.05\rho (M)}{d(u,g)}$ which assumes values greater than 1 when $u$ is very close to its pairing edge $pair(u)$.

We now define the corrective coefficient $\beta (u,g)$ that will be applied to the air-pressure forces at each vertex $u$ of region $g$ of the metaphorical map as:

Hence:

• $\mathrm{■}$

  If $\delta (u,g)=1$, i.e., $u$ marginally does not participate in a narrow passage, then $\beta (u,g)=1$.

• $\mathrm{■}$

  If $\delta (u,g)>1$, then $\beta (u,g)=1+\ln \left(\delta (u,g)\right),$ which grows logarithmically once $\delta (u,g)$ exceeds 1.

• $\mathrm{■}$

  If , then $\beta (u,g)=1-\ln \left(2-\delta (u,g)\right),$ which remains below 1 but varies smoothly as $\delta (u,g)$ decreases.

Let $u_i$ and $u_{i+1}$ be the endpoints of edge $e_i$ of region $g$ and let $\widehat{𝐫}$ be a unit vector perpendicular to $e_i$ directed towards the exterior of $g$. Recall that, the air-pressure force on $e_i$ is defined as $𝐅(e_i,g)=3P(g)s(g)\frac{\mathrm{\ell }(e_i)}{\text{circ}(g)}\widehat{𝐫}$, where $s(g)$ is the stiffness coefficient in the current iteration. Since the air-pressure force is exerted on both endpoints of $e_i$, the total air-pressure force on $e_i$ is $2\times 3P(g)s(g)\frac{\mathrm{\ell }(e_i)}{\text{circ}(g)}\widehat{𝐫}$ and the total air-pressure force of region $g$ is $2\times 3P(g)s(g)$.

The new air-pressure force, employing the above introduced corrective coefficient $\beta (\cdot ,g)$, on edge $e_i=(u_i,u_{i+1})$ is now defined as $𝐅(e_i,g)=$

Therefore, the total air-pressure force applied to region $g$ equals to ${\sum }_i𝐅(e_i,g)$. So, we have that:

$=2\times 3P(g)s(g)$, and thus, the total air-pressure force on region $g$ remains unchanged.

For the generation of test data, we followed the approach of [17] (described in detail in Algorithm 5.1 of [21] with a uniform distribution). The authors of [17] generate planar straight-line drawings based on the Delaunay triangulation of a random point set. A fraction $\text{nest}\in [0,1]$ of the points, called nesting ratio, is placed within the triangles of the initial Delaunay triangulation. It was experimentally verified in [17] that the nesting ratio has an effect on the algorithm’s performance, therefore, we also included it in our analysis. For every vertex, we generate a weight using a uniform distribution with different weight ratios of maximum to minimum weight. The above described procedure is augmented to generate non-triangulated plane graphs as follows. Following the generation of an internally triangulated plane graph, we remove a number of randomly selected internal edges in order to create non-triangulated plane graphs. We denote the ratio of removed to initial internal edges by $rem$. Note that an edge is only removed if the graph remains biconnected.

For the comparison of the performance of our algorithm (NEW-algorithm) against MS-algorithm, we examined how three parameters – the nesting ratio $nest$ (see Fig.˜4), the weight ratio $w$ (see Fig.˜5), and the total number of nodes $n$ (see Fig.˜6)–influence both algorithms. To this end, we conducted three experiments:

1. 1.

   Varying nesting ratio. For each value of $nest\in \{0,0.1,0.2,\mathrm{\dots },1.0\}$, we generated 50 graphs with $n=20$ nodes and weight ratio $w=5$.

2. 2.

   Varying weight ratio. For each $w\in \{5,10,15,20\}$, we generated 50 graphs with $n=20$ nodes and nesting ratio $nest=0$.

3. 3.

   Varying number of nodes. For each $n\in \{15,20,25,\mathrm{\dots },80\}$, we generated 50 graphs with nesting ratio $nest=0$ and weight ratio $w=5$ and we let the algorithms run for $800+10n$ iterations.

The results of every comparison follow a similar trend. Our algorithm achieves average cartographic error close to zero at the cost of a slightly higher polygon complexity. In all of our experiments (1450 in total), the recorded average normalized cartographic error (for each metaphorical map created) was in the range $[0.12\%,0.44\%]$. In comparison, the same metric for MS-algorithm is in the range $[8.8\%,24.7\%]$. The price we paid was a small increase in the average polygon complexity. The highest observed increase in average polygon complexity over all the maps was $6.9\%$ and was observed for $n=75$, where the maximum value of average polygon complexity was $19.6\%$, well below the $40\%$ value where polygons are considered to be complex [8]. The maps in our experiment that correspond to this maximum value of increase in the average polygon complexity are shown in Fig.˜7.(a-b). We observe that indeed our map’s regions are longer and, sometimes, narrower. However, in the case of smaller (or “simpler”) graphs, this increase in complexity is hardly noticeable, see e.g. Fig.˜7.(c-d). Regarding the properties of the graphs, all three parameters (nesting ratio, weight ratio, and the number of vertices) affect the polygon complexity of our produced maps.

The cost we pay for achieving average cartographic error close to zero is a small increase in the average polygon complexity. Given that our algorithm is identical to the MS-algorithm for stiffness $s_{\text{high}}=1$ (without the application of the corrective weight coefficients on the pressure forces), we evaluated our algorithm for several values of $s_{\text{high}}\in \{2,4,8\}$ (see Fig.˜8). We observed that while the average and maximum normalized cartographic error remain nearly identical for $s_{\text{high}}=4$ and $s_{\text{high}}=8$, the algorithm performs better at $s_{\text{high}}=8$ in terms of both average and maximum polygon complexity. Based on these observations, we set $s_{\text{high}}=8$ in our algorithm. This value achieves very small cartographic error while maintaining acceptable polygon complexity. Moreover, increasing $s_{\text{high}}$ beyond 8 does not lead to meaningful improvements in either evaluation metric.

Fig.˜9 shows a “heat-map” style coloring of the regions of metaphorical maps of the same graph for MS-algorithm (Fig.˜9.(a)) and our algorithm for $s_{\text{high}}\in \{2,8\}$ (Fig.˜9.(b)-(c)), demonstrating the effect of the introduction of the stiffness coefficient. These experiments reveal a monotonic decrease in the maximum/average cartographic error and a monotonic increase in maximum/average polygon complexity based on the value of $s_{\text{high}}$.

We tested our algorithm for graphs with ratio of removed edges $\text{rem}\in \{0,0.2,0.4,0.6\}$ (Fig.˜10 and 11). For each value of $\mathrm{𝑟𝑒𝑚}$, we conducted experiments on fifty graphs, each with forty nodes, a nesting ratio of zero, and a weight ratio of five. We let the algorithm run for $1200$ iterations. Recall that hole region weights were assigned according to Equation 3. Normalized cartographic error and polygon complexity were measured only for non-hole regions.

We observed that increasing the parameter rem (i.e., the fraction of removed edges) led to a slight increase across all four evaluation metrics (Fig.˜10). This can be explained by the fact that the increasing number of missing edges creates more complex patterns of adjacency, i.e. holes behave as nodes of high degree.

We also observed that holes can have narrow passages; refer to Fig.˜11.(c)-(d), which possibly can also be explained by the relatively high number of regions adjacent to a hole. We anticipate that this effect can be mitigated by using a different hole weight function and by re-engineering the applied forces.

Given that we managed to, effectively, get the average cartographic error down to zero, we did not study the effect of the initial metaphorical map used by our algorithm on the cartographic error. Instead, we focused on the polygon complexity and we examined the effect of having an initial map with good average cartographic error. As such good initial maps we considered the maps produced by the algorithm in [3] (referred to as octagonal map) which produces rectangular maps with at most 8 corners and of average cartographic error close to zero. We observed that, when using octagonal maps as initial layout, no consistent improvement was observed while the produced maps appeared to have long and skinny regions. Moreover, when the number of vertices becomes larger the metaphorical maps become harder to read due to their long, skinny, and circular shaped regions. See Fig.˜12.(a-d) and Fig.˜12.(e-h) for sample metaphorical maps of 20 and 40 regions, respectively. Finally, it is noted that our algorithm also required a larger number of iterations (about double) when initialized with such maps in order to converge to its final metaphorical map solution.