The pencil-metric is an experimental metric to compare layout-algorithms in "real" usecases. Therefore the height and width of a graph will be measured after the layout is done for a general, not bounded area. To match the given area, like an Din A4 sheet, a 10:16 screen or a simple square the total graph has to be scaled with the same factor (at least in KLay Layered). Since all nodes are layered with their real width, this scale provides a reason how big the components of the graph can be. The pencil-metric defines this scaling factor as min(rh/h,rw/w) , where h and w are the measured height and width after the layering and rh and rw are the reference height and width of the chosen usecase. For the 10:16 example two possible values would be: rh = 1920 rw=1200.
Motivation
The goals of automated graph layout is to generate or improve graphs in a way that the user can get the most important informations with the first quick view.
Besides other criteria to examine and compare the readability of a graph, like the number of edge-crossings, an important role is the actual size of the displayed graph.A graph can be easily downscaled if it is to big, but the other way around would need more space or a restriction which part of the graph should be displayed. So we consider an algorithm that creates a graph with a bigger scale superior to another with a lesser scale. This is mostly because secondary elements like labels or notes are often necessary to understand the information.
To determine this criteria in our meetings, a pencil was often used, to see if a node would cover more or less twith the compared algorithms.
We don't think that this metric can solely measure the readability of a Graph, but that it is an important factor and especially describes the effective area-usage of the algorithms.
Example Results for 10:16
Two examples of the pencil-metric are shown below. The first diagram displays the metric in an 1:1, a square, case. The second diagram was created with the resolution of our reference-screen (10:16) which is 1200:1920. The shown algorithms were post-processed with node promotion.
As expected graphs with a low node-count can be placed more often in the same area than the bigger ones. In the first picture you can see that minwidth has mostly a lower scaling-factor than the other three algorithms, which results in a lower overall size of the components.
In the second diagram you can see that the same algorithm, like minwidth, can behave differently other ratios. Like before in the beginning minwidth creates a lesser scale than the other algorithms, but with rising nodecount the results start to get better and overtake the other algorithms
Normalized Example Results for 10:16
Since one of the maingoals of this metric is the comparison of different algorithms a normalization by one reference result can give a clearer result to reason about.
In this case the pencil-metric was normalized by the result of the pencil-metric of NetworkSimplex, since this currently mostly used algorithm in KLay Layered. The data used for these diagrams is the same as in two before.
As before in the first diagram the square case is shown. In this normalized view (where NetworkSimplex is always one) one can see that graphs created by minwidth are always smaller than the other results.
Again in the 10:16 case minwidth starts with a worse result but here you can clearly see the advantages in the bigger domains.
