Question

Planar Graph

一张图，画在平面上，点不重叠、边不交叉，称作“平面图”。

先前在“ Graph ”提及了同构的概念：一张图可以挪动点与边。一张平面图，就算挪动点与边，使得点重叠、边交叉，也还是平面图。反过来说，一张图，画在平面上，挪动点与边，使得点不重叠、边不交叉，也算是平面图。

那有没有球面图呢？那有没有立体不打结图呢？应该有吧。

Euler Characteristic

凡是点、边、面这些基本元件之间的数量关係，就称作 Euler Characteristic。欧拉是第一位想到这件事情的数学家。

平面图当中，则有 V+F=E+2 这个数量关係，其中 V 代表点数、E 代表边数、F 代表面数。

进阶版本是 V+F=E+C+1，其中 C 代表连通分量数目。

你会证明吗？:-)

UVa 10178

Dual Graph

设计平面图演算法时，“对偶图”是相当重要的工具。

一张平面图当中，面与面的相邻关係表示成一张图，就得到对偶图。对偶图当中，面与面的相邻关係表示成一张图，就得到原来的平面图。

原图和对偶图可以互相转换成为对方。原图和对偶图拥有相等的资讯量，只是以不同形态呈现。

有向图的情况比较特别：对偶图从右往左穿越边；桥与自环无法判断左右，对偶图以逆时针方向穿越边。此定义亦可改成从左往右、顺时针。

运用同构的概念，挪动原图的点与边，就会得到另外一种对偶图。对偶图可能有许多种，而且不见得同构！

由于缺乏优美规律，因此谈论对偶图时，习惯忽略同构。

最特别的对偶图例子，就是桥（bridge）与自环（loop）。举例来说，原图是一棵树，对偶图是一个点加上一大堆自环；各种树对应各种自环包覆方式。

由于缺乏优美规律，因此谈论对偶图时，习惯忽略桥与自环。原图凡是无桥、无自环，对偶图即是无桥、无自环。

图论当中，有许多对偶方式。最名闻遐迩的对偶方式，就是平面对偶。于是 Dual Graph 这个名词，就留给了平面对偶所得到的图；其他对偶方式则有其他名称。

UVa 11706

Planar Graph 资料结构

http://en.wikipedia.org/wiki/Doubly_connected_edge_list

Planar Graph Recognition（Boyer & Myrvold, 2004）

http://en.wikipedia.org/wiki/Planarity_testing

要判定一张图是不是平面图，老一辈将之转换成排列顺序问题，运用 PQ Tree 或 PC Tree 资料结构求解，规则複杂难以实作。

后来出现简易的演算法，运用 Depth-first Search 就能完成，时间複杂度 O(V+E)：

http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf

UVa 10768

Mininum Spanning Tree（Matsui, 1994）

原图的最小生成森林以外的边，就是对偶图的最大生成树。

原图的每一种最小生成森林、对偶图的每一种最大生成树，一一对应。

证明：一、视树为牆。树无环，故面有出口、面皆连通。二、生成树须连通，故任两面仅能有一条通路，否则两条以上通路将切断生成树连通。三、生成森林无须连通，但是两生成子树的两面，其通路必经最外面（可想成树根），故任两面仍仅有一条通路。四、承一二三，所有面连通、任两面只有一条通路，即是生成树！五、牆最小，非牆则最大，故得最大生成树。

演算法原理类似“ Borůvka's Algorithm ”，同时考虑原图和对偶图，同时计算原图的最小生成树、对偶图的最大生成树。

一、随时删除所有自己连向自己的边，也就是删除所有自环。
二、重複以下步骤 V 次：
　口、原图加上对偶图，一定找得到一个度数小于 4 的点，称作 a 点。
　口、如果 a 点在原图上：
　　甲、原图 a 点所属的生成子树，找权重最小的联外边 ab。
　　乙、原图的最小生成树有边 ab。
　　丙、原图收缩边 ab、对偶图删除边 ab。两图随时保持对偶。
　口、如果 a 点在对偶图上：
　　甲、对偶图 a 点所属的生成子树，找权重最大的联外边 ab。
　　乙、对偶图的最大生成树有边 ab。
　　丙、对偶图收缩边 ab、原图删除边 ab。两图随时保持对偶。

因为度数小于 4，找最小邻边的时间複杂度就下降为 O(1)，总时间複杂度就下降为 O(V+E)，到达了下限。

平面图：V+F=E+C+1
原图加上对偶图的总度数：2E + 2E' = 4E
原图加上对偶图的总点数：V + V' = V + F = E+C+1
原图加上对偶图，一个点的平均度数：4E / (E+C+1) < 4
原图加上对偶图，一定至少有一个点，其度数小于等于平均度数，也就是小于 4。

由于要维护原图和对偶图的资料结构，还要随时找到度数小于 4 的点，所以此演算法的实际运行速度，远比一般图的最小生成树演算法来得慢。

儘管此演算法并不实用，但是此演算法开启了一条道路，让我们知道各种图论问题一旦搬到平面图上，只要运用对偶图、度数等等性质，时间複杂度就会有很大的改进。

至于有向图的版本，我不知道有没有人研究。

Shortest Path

http://courses.csail.mit.edu/6.889/

ICPC 6438

Minimum Cut / Maximum Flow

http://www.cnblogs.com/yejinru/archive/2013/04/19/3031731.html

Klein

Multiple-source shortest paths in planar graphs
build O(nlogn)  query O(logn)

Multiple-Source Single-Sink Maximum Flow in
Directed Planar Graphs in O(diameter * nlogn) Time
http://arxiv.org/pdf/1104.4728.pdf

ICPC 3661

Clique

http://tmtacm.blogspot.tw/2016/01/i.html

备忘

平面图判定           O(n)
最小生成树           O(n)
st 最短路径（无负边)   O(n * sqrt(log(n)))
st 最短路径（负边)     O(n^1.5)
st 最大割             O(n^1.5 * log(n))
st 最小割             = st 最短路径
st 最大流             = st 最短路径
最小割               = ∅-join
最小环基底           = Gomory–Hu tree
st 严格次短路径       O(n^3)
完美匹配计数         FKT algorithm
G is Eulerian iff dual(G) is bipartite.

Intersection Graph

平面图是 disk graph/coin graph
平面图是平面上一堆线段的 intersection graph

平面图都可以表示成二维线段相交的 intersection graph
二分平面图都可以表示成水平垂直线段相交的 intersection graph
没有三角形的平面图可以表示成三方向线段相交的 intersection graph，3-colorable

Euclidean Graph

Euclidean Graph

边的权重，等于二维平面的直线距离。请参考计算几何领域。

儘管 Euclidean Graph 是二维平面上的图，但是它跟前面提到的平面图，没有任何关係。