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$$

$$ \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.


What 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)$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.