原论文：https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/Efficient Planarity.pdf
一种 \(O(n)\) 判断图平面性的做法
两个引理
引理 1：一个图是平面图的必要条件是 \(m\le 3n-6\)
广为人知
引理 2：在一个平面图中，设 \(p_1,p_2,p_3\) 是三条从 \(x\) 到 \(y\) 的路径，任意两条只有 \(x,y\) 两个公共点，设其第一条边分别是 \((x,v_1),(x,v_2),(x,v_3)\)，其最后一条边分别是 \((w_1,y),(w_2,y),(w_3,y)\)，若 \(x\) 周围的边按照顺时针顺序依次是 \((x,v_1),(x,v_2),(x,v_3)\)，那么 \(y\) 周围的边按照顺时针顺序是 \((w_1,y),(w_3,y),(w_2,y)\)
证明可以根据 Jordan curve theorem 直接得到，而其证明比较复杂
概述
原论文的图都是从下往上画的，于是下面想象一颗搜索树的时候尽量让根在最底下
对于图 \(G\)，显然他是一个平面图等价于他的所有点双连通分量都是平面图，可以把每个双连通分量围绕在割点周围
那么现在讨论 \(G\) 是一个点双连通图的情况
对 \(G\) dfs 建出 dfs 树，记录下 dfs 序并将 \(u\) 重标号为 \(dfn(u)\)，然后将每条树边重定向为 dfs 树上的父亲指向儿子，每条返祖边重定向为后代指向祖先（无向图的 dfs 树只有树边和返祖边）
下面的所有讨论都基于如上的假设
现在找到 \(G\) 中的一个环：\(C:1\rightarrow u_1\rightarrow u_2\rightarrow \cdots \rightarrow u_n \rightarrow 1\)，在整个环上，前面的边都是树边，只有 \(u_n \rightarrow 1\) 是返祖边
现在删掉 \(C\)，那么 \(G\) 中会剩下若干个连通块，我们称之为 Segment；对于每个 Segment，要么是由单一的一个返祖边组成，要么是某 \(u_i\) 的一个儿子 \(v\) 以及他子树中的所有边（从子树出发的所有树边、返祖边）以及边 \((u_i,v)\) 组成
由于每个 Segment 中不会存在形如 \(x\rightarrow u_i\rightarrow y\) 的路径，所以每个 Segment 都会全部在环 \(C\) 的内侧或外侧
下面用 \(x\rightarrow y\) 表示一条从 \(x\) 到 \(y\) 的边，用 \(x\Rightarrow y\) 表示一条 \(x\) 到 \(y\) 的经过多条边的路径
考虑寻找双连通分量时的 tarjan 算法，定义出 \(low(u)\)，类似的，定义出严格次小值 \(low2(u)\)（当 \(low(u)=low2(u)=u\) 时，可忽略严格的要求）
考虑每个 Segment 对应了一个环 \(C_v:u_i\rightarrow v\Rightarrow low(v)\Rightarrow u_i\)，我们将这个环作为此 Segment 的 外轮廓，那么若按照从外往里的顺序嵌入，则这个 Segment 的其他部分都被嵌入到了 \(C_v\) 的里面，因此就不会影响到其他的 Segment
那么有一个大概的思路：
- 依次考虑 \(G\) 的每一个 Segment，所在嵌入环 \(C\) 和其他已经嵌入的 Segment 后，该 Segment 的外轮廓 \(C_v\) 不能在被嵌入，则 \(G\) 不是平面图
- 否则，尝试递归判断该 Segment 是否可以平面嵌入
- 具体的，就是把 \(C_v\) 当作递归下去后的环 \(C\)，然后删掉他就又得到了若干小 Segment
Pathfinding
首先考虑如何找到一条合适的路径 \(v\Rightarrow low(v)\) 将其作为外轮廓的一部分
一个想法是让 \(low\) 最小的边在邻接表中先被遍历到，然后沿着邻接表往下走
具体的，考虑给当前 Segment 的边集划分为若干个子集，每个子集是一条路径（或者按照上文说是一个轮廓），先给一个点的所有出边进行排序，定义边权：
对这些边权从小到大桶排序来保证复杂度
引入 \(low2\) 是因为要把 \(low2\) 更小的路径放在内侧防止它把别的路径挡住（具体的用处会在后面的某些证明中用到）
排序后遍历时，依次经过每一条边：经过一条树边，把他加进正在构建的那条路径中；经过返祖边，将这条边作为目前构建的这条路径的最后一条边，下一条经过的边会在一个新的路径中
如图（注意这个图是从下往上画的搜索树，左图是找到的若干路径，右图是划分出的若干 Segment）：
那么这些路径的形态，就是若干条（可能为零）树边加上一条返祖边结尾，因为图是双连通的，那么有 \(low(1)=1\) 以及 \(low(u)<u(u\neq 1)\)
于是对于路径 \(p:s\Rightarrow t\) 必定是 \(s=t=1\)，形成一个环；或者 \(p\) 是一条简单路径，\(t\) 是 \(s\) 的祖先，路径 \(t\Rightarrow s\) 完全由树边组成
考虑其他性质：
性质 1：若有路径 \(p:s\Rightarrow f\)，那么当走过这个路径上的第一条边时，考虑所有还没有被用到的返祖边（每条路径对应一个返祖边），\(f\) 是通过 \(s\) 的某后代的一条返祖边可以到达的最小的点；对于路径中的一个不是端点的节点 \(x\)，\(f\) 是他可以到达的最小点
显然，这两点都可以通过对邻接表的排序方式来简单理解
性质 2：若有 \(p_1:s_1\Rightarrow f_1,p_2:s_2\Rightarrow f_2\) 是按照如上方式生成的两条路径，如果 \(p_1\) 在 \(p_2\) 之前被生成，且 \(s_1\) 是 \(s_2\) 的祖先，那么有 \(f_1\le f_2\)
从性质 1 进一步扩展，\(p_2\) 结束的那条返祖边（\(f_2\) 结尾）一定是从 \(s_1\) 的某个后代发出的，而 \(p_1\) 先生成所有这条返祖边还没被用，于是他不可能比 \(f_1\) 还得，就有了 \(f_1\le f_2\)
性质 3：对于两条起点终点相同的路径 \(p_1:s\Rightarrow f,p_2:s\Rightarrow f\)，设 \(v_1,v_2\) 分别是两条路径上的第二个点，若 \(p_1\) 在 \(p_2\) 之前被生成，且 \(v_1\neq f,low2(v_1)<s\)，则有 \(v_2\neq f\) 以及 \(low2(v_2)<s\)
由于产生顺序，临界表中 \(v_2\) 被排序在了 \(v_1\) 的后面，而 \(low(v_1)=low(v_2)=f\)，则可以得知 \(v_2\neq f\) 以及 \(low2(v_2)<s\)
这个性质在一定程度上体现了引入 \(low2\) 的必要性
Embedding the Path
按照上面方法找到的若干条路径，显然每条路径必定处于同一个 Segment 中
一个 Segment 包含的所有路径一定是被连续生成的，且 Segment 的被发现顺序按照 \(u_i\) 从大到小（考虑上面的图）
考虑加入一个新 Segment \(S\) 时，环 \(C\) 和其他在他之前发现的 Segment 都已经被嵌入，检查其第一条路径是否可以嵌入，若可以，再递归判断剩下的
之前说过一个 Segment 必定全部被嵌入到环 \(C\) 的同一侧，后面描述某由 \(u_i\) 的一个儿子 \(v\) 的子树中的所有边组成的 Segment \(S\) 被嵌入到了环 \(C\) 的左边，意思是围绕 \(u_i\) 的点按照顺时针分别是 \((u_{i-1},u_i),(u_i,v),(u_i,u_{i+1})\)
描述某 Segment \(S\) 被嵌入到了环 \(C\) 的右边，意思是围绕 \(u_i\) 的点按照顺时针分别是 \((u_{i-1},u_i),(u_i,u_{i+1}),(u_i,v)\)
（再次说明想象一颗搜索树的时候让根在下面）
有以下定理
考虑某条划分出的路径 \(p:u_i\Rightarrow u_j\)，他可以被嵌入到环的左边（右边）当且仅当不存在一条返祖边 \((x,u_k)\) 在此之前被嵌入到了环的左边（右边），且满足\(v_j<v_k<v_i\)
简单证明：
若不存在满足条件的返祖边，那么只要把 \(p\) 和环 \(C\) 贴的足够近，就一定可以嵌入而不影响其他部分
若存在返祖边 \((x,u_k)\)，可能有 \(x\) 就在环上也就是 \(x=u_l\)，也可能有 \((x,u_k)\) 在某 Segment \(S'\) 上，此时设 \(S'\) 的第一条边是 \((u_l,v)\)
由于 \(S'\) 先被发现，考虑生成路径的顺序，有 \(u_l\ge u_i\)，下面以往左边嵌入为例分类讨论（下图中 \(v\) 数组对应文中 \(u\) 数组）：
- \(u_l>u_i\)，如图 (a)，考虑从 \(u_j\) 到 \(u_l\) 的树边，构成了三条从 \(u_i\) 到 \(u_k\) 的边，必定相交，违反引理 2
- \(u_l=u_i\)，路径 \(p_1:u_l\Rightarrow u_m\) 是 Segment \(S'\) 中的第一条路径，根据之前 Pathfinding 中的性质 3，有 \(u_m\le u_j\)
- \(x=u_l\)，就是返祖边的起点也在环上，此时根据给出边的排序方式必定有 \(u_k\le u_j\)，矛盾；于是后面不用再考虑这种情况，Segment \(S'\) 至少要有两条边，也就是了 \(v\neq u_m\)
- \(u_m<u_j\)，如图 (b)，考虑 \(p:u_i\Rightarrow u_j\) 以及从 \(u_k\) 到 \(u_i\) 的所有树边，会产生三条从 \(v_k\) 到 \(v_i\) 的路径违反引理 2
- \(u_m=u_j\)，如图 (c)，之前说 \(v\) 是 \(p_1\) 中的第二条边，现在再设 \(p\) 上的第二条边是 \(y\)，那么由于 \(v\neq u_m,low2(v)\le u_k< u_l\)，于是现在对 \(p,p_1\) 应用 Pathfinding 中的性质 3，得到 \(y\neq u_j,low2(y)<u_m\)
更进一步，由于 \(low(y)=v_j\)，可以得知 \(low2(y)>v_j\)，于是 \(low2(y)\) 的位置就如图所示了（但 \(low2(y)\) 和 \(u_k\) 的位置关系其实是未确定的）
于是可以构造出三条从 \(v_k\) 到 \(low2(y)\) 的路径（一条走 \(p\)，一条 \(p_1\)，一条他们之间的树边）
于是就可以根据以上定理判断一条路径能否被嵌入
找到要嵌入的 Segment \(S\) 中的第一条路径 \(p\)，尝试将 \(p\) 嵌入到环 \(C\) 的左侧，检查所有返祖边来确定能不能直接将 \(p\) 嵌入；如果不能，把所有挡住了 \(p\) 的返祖边（也就是边 \((x,u_k)\)）从 \(C\) 的左侧转移到右侧，如果这样搞完产生了其他冲突（某些在右侧的边需要移动到左侧）就说明 \(G\) 不是平面图
否则就递归嵌入其他路径
如何维护？
考虑 \(L\) 按顺序存入满足 \(1\Rightarrow u_k\Rightarrow u_i\)，且有返祖边 \((x,u_k)\) 被嵌入到了环的左边的 \(u_k\)，当然若存在多条这样的返祖边，同一个 \(u_k\) 可能在其中出现多次
同理维护 \(R\)
- 当结束了 \(u_{i+1}\) 的所有 Segment 的嵌入，从 \(L,R\) 中删去 \(u_i\)
- 若 \(p:s\Rightarrow f\) 是 Segment \(S\) 的第一条线段，且 \(f\neq 1\)，那么嵌入 \(p\) 后将 \(f\) 加入 \(L\) 或 \(R\) 中
- \(p\) 能被嵌入到左边（右边）当且仅当 \(L(R)\) 中最大元素小于等于 \(f\)
- 当嵌入产生冲突，需要把 \(L(R)\) 中的一部分点转移到 \(R(L)\) 中
- 当确定了一条返祖边在左（右）边后，他要求和他在同一个 Segment 中的所有返祖边在同一侧，同时要求另一些返祖边在异侧。于是定义一个 block 是一个极大的，满足其中一个的位置（左或右）被确定，剩下的都被确定的集合
发现这个 \(L,R\) 就是栈，第二个操作能用栈做的原因是要插入的话一定是最大的，所以直接放到栈顶
对于一个 block，有如下性质：
对于 block \(B\)，\(B\cap L(B\cap R)\) 在 \(L(R)\) 上是连续的一段
基于此性质，可以用 \((x,y)\) 来维护一个 block，分别表示他在 \(L\) 和 \(R\) 中的最小元素
那么嵌入 \(p\) 前先把冲突的交换掉，然后再把那些冲突的 \(u_k\) 的 block 和 \(p\) 的 block 合并起来
可以对过程归纳得到上面的性质
回溯的处理
递归下去是简单的，但当递归处理完某个 Segment 时，由于选定环的不同会带来一些问题
设原来选定的环 \(C\) 是 \(u_1\rightarrow u_2\rightarrow \cdots\rightarrow u_n\rightarrow u_1\)，而递归进某 Segment 后选定的环 \(C\) 是 \(u_i\rightarrow v\Rightarrow u_j\Rightarrow u_i\)
设维护每个 block 的点对的栈叫做 \(B\)
那么 \(L,G,B\) 中，所有大于等于 \(u_i\) 的部分与原来的 \(C\) 无关，可以删掉
所有在区间 \((u_j,u_i)\) 中的部分，由于在递归进新环时可能被放在了新环的不同侧，但此时要求他在原环的同一侧（因为处于同一个 Segment 中），那么就要把他往同一侧移动并合并 block，移动不了就不是平面图
实现细节
由于这些合并操作以及如上 block 的性质的存在，\(L,R\) 用链表维护更好
用一个栈 \(B\) 来对于每个 block 维护点对 \((x,y)\)，若某 block 不存在 \(L(R)\) 中的点，那么 \(x(y)\) 的值就是 \(0\)
\(R\) 中需要加入一些特殊标记来区分原来环 \(C\) 的信息和递归下去新的环 \(C\) 的信息