Context:This question rises from the paper Methods for Visual Understanding of Hierarchical System Structures by Kozo Sugiyama, Shojiro Tagawa and Mitsuhiko Toda, which lays out a framework (the Sugiyama framework), for hierarchical graph drawing. In the paper, Sugiyama et al. introduce the Barycenter Method for reducing crossings, which requires computing the upper and lower barycenters, defined in equation 9 on page 113.$$B^U_{ik}=\sum\limits_{j=1}^px(v^{i-1}_j)m^{(i-1)}_{jk} / C^U_{ik},\quad k=1,\dots,\lvert V_i\rvert$$$$B^L_{ik}=\sum\limits_{l=1}^qx(v^{i+1}_l)m^{(i)}_{kl} / C^L_{ik},\quad k=1,\dots,\lvert V_i\rvert$$where:$$\begin{align}B^L_{ik} &= \text{upper barycenter of a vertex } v^i_k\\B^U_{ik} &= \text{lower barycenter of a vertex } v^i_k\\C^L_{ik} &= \text{lower connectivity of a vertex } v^i_k\\C^U_{ik} &= \text{upper connectivity of a vertex } v^i_k\\E_i &= E_i \subset E,\quad e_i =(v, w) \in E_i \text{ if } v\in \sigma_i \lor w\in \sigma_i  \\i &= \text{is the index of the layer}\\M^{(i)} &= \text{is the matrix realization of layer $i$}\\m^{(i)}_{kl} &= \begin{cases}1&\text{if } (v_k,w_l) \in E_i\\0&\text{otherwise}\end{cases}\\p &=\lvert V_{i-1}\rvert\\q &=\lvert V_{i+1}\rvert\\ \sigma_i &= \text{an }\textit{order }\text{of $V_i$}\\v^i_k &= \text{is the } k^{\text{th}} \text{ vertex in the } i^{\text{th}}\text{ level}\\x(v) &= \text{is the horizontal position of a vertex $v$}\end{align}$$The definition of matrix realization is found in equation q on page 112.QuestionWhat is $x(v)$? Yes it is the horizontal position of a vertex $v$, but what is that? My confusion stems from the statement of the upper-/lower- barycenter for vertex $v^i_k$, which can be calculated for $k = 1,\dots,\lvert V_i \rvert$.$V_i$ is a set, hence lacking order, which makes me presume - perhaps falsely - that it is in reference to the ordering of $V_i$, which is $\sigma_i$. If the horizontal position of a vertex $v$ was simply its position in its respective layer's ordering, then $x(v^i_k) = k$. Since the BC method hinges upon these calculations, what is $x(v)$?
Sugiyama's algorithm: ambiguity in Barycentric Method for arc (edge) crossing reduction?
algorithms;graphs;graph theory;graphics