# Graph layout (图布局质量)

## 图布局质量判定规则

• 首要规则：最小化边交叉数目
因为当图中出现很多边交叉时，会导致用户可视化理解图数据能力显著下降
• 次要规则：最小化边曲折度
图中有较多的曲折边，会导致用户可视化理解图数据能力一定程度地下降，可以想象尤其当图中出现非常多的曲折边时，那将是一种灾难。

## 图布局算法

### Tutte 基于重心的图布局算法

Tutte’s barycenter algorithm

Input:

- A graph G = (V, E) with node set V and edge set E


Output:

- A straight-line drawing p of G

• Step 1. Choose a subset A of V
• Step 2. Choose a location $p(a)=(x_{a}, y_{b})$ for each vertex $a$ $\epsilon$ $A$
• Step 3. For all $u$ $\epsilon$ $V - A$, choose $p(u)$ bywhere the sum is over all neighbors $v$ of $u$.

### 基于Planarity的图布局算法

Planar graph是可以在平面展示但是没有交叉边的图（其中边与边可以在端点相交）。

A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.

• 层次图布局

• 正交图布局

• 辐射状图布局

# Reference

[1]. A heuristics for graph drawing. Congr. Peter Eades. Numer. 42 (1984) 149-160.
[2]. How to draw a graph, Tutte, W. T. Proceedings of the London Mathematical Society, 13: 743–767, 1963.
[3]. Structure-Based Suggestive Exploration: A New Approach for Effective Exploration of Large Networks. Wei Chen, Fangzhou Guo, Dongming Han, Jiacheng Pan, Xiaotao Nie, Jiazhi Xia, Xiaolong Zhang. IEEE Transactions on Visualization and Computer Graphics (Special issue on IEEE VAST 2018), 2019.