6. Calculating metrics of arrangements
As it might seem obvious to most readers, we can calculate values (or metrics) on these arrangements. These values depend on the graph drawn and on the arrangement of its vertices. Moreover, some metrics can't be calculated on certain types of arrangements. For example, the sum of edge lengths (see below) can't be calculated on circular arrangements.
The calculation of a metric is enabled by checking the corresponding checkbox.
In an arrangement \pi of a graph G each edge uv has a length, defined as the distance between the endpoints d_{\pi}(u,v). Recall that \pi(u) denotes the position 1 <= \pi(u) <= n.
The sum of all edge lengths is, then
D_{\pi}(G) = \sum_{uv\in E(G)} d_{\pi}(u,v)
This value can be calculated by the ipelet and be displayed beneath the arrangement. This is done by checking the appropriate checkbox in the ipelet's dialog. For example, for the tree described with the head vector
0 1 2 3 4 5 6 1 8 9 10 11 12
we can calculate D without arrangement giving
But we can also calculate it with the arrangement
6 5 4 3 2 1 0 7 8 9 10 11 12
which gives
In linear arrangements, the length of an edge connecting vertices u and v is defined as
d_{\pi}(u,v) = |\pi(u) - \pi(v)|
In circular arrangements, the length of an edge connecting vertices u and v is defined as
d_{\pi}(u,v) = minimum(i_{\pi}(u,v), o_{\pi}(u,v))
i_{\pi}(u,v) = |\pi(u) - \pi(v)|
o_{\pi}(u,v) = n - |\pi(u) - \pi(v)|
where i_{\pi}(u,v) is the counterclockwise distance function (the same for linear arrangements), and o_{\pi}(u,v) is the clockwise distance function.
The definition of the number of edge crossings changes slightly depending on the arrangement.
In both linear and circular arrangements, two edges cross if their positions interleave, i.e., two edges e_1={s,t} and e_2={u,v} cross iff (assuming w.l.o.g. that \pi(s) < \pi(t) and \pi(u) < \pi(v)),
\pi(s) < \pi(u) < \pi(t) < \pi(v) or \pi(u) < \pi(s) < \pi(v) < \pi(t)
For example, the input
gives the following output (the arrangements have been reorganized a bit)
In a bipartite arrangement of a (bipartite) graph G=(V_0\cup V_1, E), two edges e_1={s,t} and e_2={u,v} cross iff (assuming w.l.o.g. that \pi(s) < \pi(t) and \pi(u) < \pi(v), s,u\in V_0, t,v\in V_1),
\pi(s)<\pi(u), \pi(v)<\pi(t) or \pi(u)<\pi(s), \pi(t)<\pi(v)