由于离散课需要回课，就去学了Hopcroft和Tarjan老爷子在1974年提出的 $O(V)$ 时间内判断一个图是否是平面图的算法，然后上课的时候讲。原文是 John Hopcroft and Robert Tarjan. 1974. Efficient Planarity Testing.J. ACM21, 4 (October 1974), 549-568. 这是链接。

用了好一些时间才完全理解整个算法。想懂之后其实并不难，但真真实实非常巧妙。

感觉论文读起来困难是因为一开始没有把握到算法的整体思想，所以一度看的怀疑人生。一旦知道文章在干嘛，很多地方读起来就十分自然了。

课上听某同学讲，某年清华集训貌似就出了一道平面图判定的模板题，也不清楚标算是不是用的这个算法。

一些记号

简单路径：每个点至多被经过一次。

环：除起点外，每个点至多被经过一次。

割点：删掉该点后原图不再连通。

双连通图：连通且不包含割点的图。

$p:v{\Rightarrow }^{\ast }w$：$p$ 是一条从 $v$ 到 $w$ 的路径。

树：根为 $r$ 的有向图 $T$，从 $r$ 出发可以到达所有点， $r$ 没有入边，其余每个点恰好有一条入边。

$v\to w$：$T$ 中一条 $v$ 到 $w$ 的边，称 $v$ 为 $w$ 的父亲， $w$ 为 $v$ 的儿子。

$v{\to }^{\ast }w$：$T$ 中 $v$ 到 $w$ 的路径，称 $v$ 为 $w$ 的祖先，$w$ 为 $v$ 的后代。

$dfs$ 树

设 $G$ 是一个连通无向图。从一个点开始对 $G$ 做 $dfs$，令经过的边为树边，得到 $G$ 的生成树 $T$，称 $T$ 为 $G$ 的 $dfs$ 树。

若边 $(v,w)$ 不是树边，且 $v$ 和 $w$ 在 $T$ 中有祖先关系，不妨设 $w$ 是 $v$ 的祖先，则称 $(v,w)$ 为一条返祖边，记为 $v-\to w$。

因为是通过 $dfs$ 遍历图 $G$，所以 $G$ 中的每一条非树边必然是返祖边。

令 $dfn(x)$ 表示 $x$ 被到达的时刻，$low(x)$ 表示通过 $x$ 的子树中的返祖边能到达的节点的 $dfn$ 的最小值，形式化定义就是 $$low(x)=\min \{dfn(x),\underset{(u,v)\in E_f,u\in subtree(x)}{\min }dfn(v)\}$$

其中 $E_f$ 表示返祖边构成的集合。同时令 $low2(x)$ 表示次小值。

算法思想

对于一个连通图 $G$，它是平面图当且仅当它的每一个点双连通分量均为平面图。因此只需要考虑一个双连通图的平面图判定问题。

先找出 $G$ 的 $dfs$ 树 $T$，将每个点 $x$ 重标号为 $dfn(x)$，并将边重定向：令树边从父亲指向儿子，返祖边从后代指向祖先。找到 $G$ 中的一个环 $c:1\to v_1\to v_2\to \cdots \to v_n-\to 1$，环中只有最后一条边是返祖边。删掉 $c$ 后会得到很多个连通块，称之为 segment。每个 segment 要么是一条 $v_i{\to }^{\ast }{v}_j$ 的返祖边，要么由某个 $v_i$ 的儿子 $u$ 的子树中的所有边（包括返祖边）组成。则每个 segment 最后必然全落在 $c$ 的内侧或外侧。

每个 segment 都对应一个环 $c_u:v_i\to u{\Rightarrow }^{\ast }low(u){\to }^{\ast }{v}_i$，可将 $c_u$ 看作该 segment 的外轮廓。按照从外向内的顺序嵌入 segment，则该 segment 的其他部分可被嵌入到 $c_u$ 的内部，不影响其他已经被嵌入的 segment。

对于一个新加入的 segment，先考虑在已经嵌入了环 $c$ 和前面被加入的 segment 的基础上，其外轮廓能否被嵌入到平面中。若不能嵌入，则 $G$ 不是平面图。否则保留 $c_u$ 和 segment 的其余部分，递归判定能否嵌入到平面中：把 $c_u$ 看作递归后的环 $c$，删掉 $c_u$ 后又形成了若干个 segment，然后继续重复上述过程。

以上是算法的大概思想，接下来考虑具体的实现细节。

Sorting The Children

对于一个 segment，现要选择一条从 $u$ 到 $low(u)$ 的路径，并将其视为该 segment 的外轮廓。容易想到可以把每个点邻接表中的元素按 $low$ 从小到大排序，然后沿着排序后邻接表一直往下走。具体来说，我们给每条边分配一个边权：

$$\varphi ((v,w))=\{\begin{array}{ll}2w& v-\to w\\ 2low(w)& v\to w\wedge low2(w)\ge v\\ 2low(w)+1& v\to w\wedge low2(w)<v\end{array}$$

然后把邻接表中的边按边权递增顺序排列。

为什么要引入 $low2$ 呢？感性地讲，当两个点的 $low$ 相同时，若把 $low2$ 较小的路径作为外轮廓，则会把另一条路径挡住。因此我们希望把 $low2$ 较小的路径放在内侧。

Pathfinding

现在想要把边集划分成若干个部分，每个部分是一条路径。我们沿着排序后的邻接表做 $dfs$，每遇到一条树边就将其加入到当前的路径当中；遇到一条返祖边则划分出一条路径，然后开始一条新的路径。那么每条路径是由若干条树边（可能没有）和一条返祖边组成，每条边恰好属于一条路径，且每条路径和返祖边构成一一对应关系。

代码实现如下：

void pathfinder(int v) {
  for (int w : G[v]) {
    if (dfn[v] < dfn[w]) {
      if (s == 0) {
        s = v;
        //start a new path
      }
      //add (v,w) to current path
      pathfinder(w);
    } else { //(v,w) is a frond
      if (s == 0) {
        s = v;
        //start new path
      }
      //add (v,w) to current path
      //output current path
      s = 0;
    }
  }
}

这样划分出来的路径有一些很好的性质。

定理1

设 $p:s{\Rightarrow }^{\ast }f$ 是一条被划分出的路径，当走过该路径上的第一条边时，$f$ 是 $s$ 的子树中还没被遍历的返祖边指向的最小节点。对于路径中的非端点节点 $v$，$f$ 是 $v$ 的子树中的返祖边指向的最小节点。

证明 通过对邻接表的排序方式即可证明。

推论 令 $p_1:s_1{\Rightarrow }^{\ast }{f}_1,s_2{\Rightarrow }^{\ast }{f}^2$ 是两条被划分出的路径，且 $p_1$ 在 $p_2$ 之前出现，若 $s_1$ 是 $s_2$ 的祖先，则 $f_1\le f_2$。

定理2

设 $p:s{\Rightarrow }^{\ast }f$ 是一条被划分出的路径，那么 $f{\to }^{\ast }s$ 仅由树边组成。若 $p$ 是第一条被划分出的路径，则 $p$ 是一个环。否则 $p$ 是一条简单路径。

证明 点双连通性保证了 $low(1)=1$，且除了根节点外，均有 $low(v)<v$。由定理1可知成立。

Embedding The Paths

接下来就可以考虑如何嵌入 segment 了。

第一条被生成的路径是一个环 $c:1\to v_1\to \cdots \to v_n-\to 1$，删掉?后得到若干 segment，每个 segment 是某条返祖边 $v_i-\to v_j$，或由某个 $v_i$ 的儿子 $u$ 的子树中的边（包括返祖边）组成。

每个 segment 必然全被嵌入到 $c$ 的外侧或内侧。因为一个 segment 中不存在这样的路径 $x\to v_i\to y$，其中 $v_i$ 是环 $c$ 上的点，且 $(x,v_i),(v_i,y)$ 为该 segment 中的边。若该 segment 有两条边被嵌入到 $c$ 的两侧，必然有一条与环相交的路径，矛盾。

注意到划分出的每条路径恰好位于一个 segment 中，且某个 segment 中的路径是被连续生成的，且 segment 是按照 $v_i$ 递减的顺序被访问。那么我们按照被访问的顺序逐个加入 segment。加入一个新的 segment 时，先判定其中第一条路经能否嵌入，再递归处理其他部分。

判定路径能否嵌入需要用到以下定理：

定理3

对于两条起点和终点相同的路径 $p_1:s{\Rightarrow }^{\ast }f,p_2:s{\Rightarrow }^{\ast }f$，令 $v_1,v_2$ 为这两条路径的第二个节点，若 $p_1$ 先被产生，$v_1\ne f$ 且 $low2(v_1)<s$，则 $v_2\ne f$ 且 $low2(v_2)<s$。

证明 因为在 $s$ 的邻接表中 $v_2$ 排在 $v_1$ 的后面，且 $low(v_1)=low(v_2)=f$，因此必有 $low2(v_2)<s$。

定理4

若在 segment $S$ 之前被访问的 segment 均已被嵌入，则 $S$ 中的第一条路径 $p:v_i{\Rightarrow }^{\ast }{v}_j$ 能被嵌入到 $c$ 的外（内）侧，当且仅当不存在一条已经被嵌入到外（内）侧的返祖边 $(x,v_k)$（称为 $v_k$ 被占用）满足 $v_j<v_k<v_i$。

感性证明 若不存在这样的返祖边，则必然可以嵌入 $p$。反之，因为我们是按照从外到内的顺序嵌入 segment，若某个 segment 已经占用了 $v_k$，那么内侧 segment 的轮廓就无法跨越 $v_k$。

证明 若不存在这样的返祖边，则必然可以嵌入 $p$。反之，若存在一条已经被加入的返祖边 $(x,v_k)$ 满足 $v_j<v_k<v_i$，设这条边所在的 segment $S^{\prime }$ 中被经过的第一条边为 $(v_l,w)$，由 $S^{\prime }$ 在 $S$ 之前被访问可知 $v_l\ge v_i$。下面分几种情况讨论：

Case1 $v_l>v_i$，如图 $(a)$ 所示。那么图中存在的三条 $v_i$ 到 $v_k$ 的路径必然会交叉。

Case2 $v_l=v_i$，令 $p_1:v_l\Rightarrow v_m$ 是 $S^{\prime }$ 中第一条被生成的路径，则必有 $v_m\le v_j$。下面又分两种情况：

Subcase1 $v_m<v_j$，如图 $(b)$ 所示。那么图中存在的三条 $v_i$ 到 $v_k$ 的路径也必然会相交。

Subcase2 $v_m=v_j$，如图 $c$ 所示。令 $y$ 为 $p$ 上的第二个点。因为 $w$ 是 $p_1$ 上的第二个点，$w\ne v_m$，$low2(w)\le v_k<v_l$，且 $p$ 在 $p_1$ 后被生成，则必有
$y\ne v_j$ 且 $low2(y)<v_i$。由 $low(y)=v_j$ 可知 $low2(y)>v_j$。那么由图中可以看出，无论 $p,p_1$ 哪条路径放在外侧，都会有相交的边。

有了以上定理，就容易判断一条路径能否被嵌入了。设新加入的 segment 为 $S$，若 $S$ 之前被访问的 segment 均已被嵌入，令 $p:v_i{\Rightarrow }^{\ast }{v}_j$ 是 $S$ 中的第一条路径，考虑强制把 $p$ 嵌入到环 $c$ 的外侧。若存在某条已被加入的外侧返祖边 $(x,v_k)$ 满足 $v_j<v_k<v_i$，则需要把一些 segment 从 $c$ 的外侧移到内侧。

若移动后仍然冲突，表明 $G$ 不是平面图。否则嵌入 $p$ 后，再递归判断 $S$ 的其他部分能否被嵌入。

注意到对于 $S$ 和与 $S$ 冲突的 segment，若确定其中一个 segment 的位置（内侧还是外侧）后，另外的 segment 的位置也确定了。容易想到可以把这些 segment 合并到一起处理。我们称若干个 segment 合并形成的集合为一个 block。当移动一个 segment 时，与其在同一个 block 的 segment 均要被移动。

为了判断 $p$ 能否被嵌入，我们需要维护 $v_i$ 到根的路径上，$c$ 的内侧和外侧所有被占用的点的集合 $R,L$。

那么加入一条路径的过程为，找到所有占用 $v_k(v_j<v_k<v_i)$ 的 segment 所在的 block，把这些 block 在 $L,R$ 中的点互换位置，如果仍然冲突则 $G$ 不是平面图。否则把所有上述 block 和该路径所在的 block 合并为一个 block。

对于一个 block，我们关心这个 block 在在 $L,R$ 中有哪些点，因为移动一个 block 时需要交换这个 block 在 $L$ 中和 $R$ 中的点。直接暴力交换的话会很慢，而每个 block 中的点有一些特殊的性质：

定理5

对于一个 block，它在 $L(R)$ 中的点 $L^{\prime }(R^{\prime })$ 是 $L(R)$ 中连续的一段，且 $L^{\prime }\cup R^{\prime }$ 是 $L\cup R$ 中连续的一段。

证明 由上述做法可知每次合并的一定是一段连续的 block，由归纳可知该定理成立。

因此我们可以用二元组 $(x,y)$ 来表示一个 block，其中 $x$ 表示 block 在?中的最小元素所在的位置，$y$ 表示 block 在 $R$ 中的最小元素所在的位置，用一个栈 $B$ 来维护 $(x,y)$。同时如果用链表来维护 $L,R$，就能在 $O(1)$ 的时间内完成交换。

回溯处理

递归处理完一个 segment 后，由于递归前和递归后的环不相同，需要做一些修改。设原来的环为 $v_1\to \cdots \to v_n-\to v_1$，新的环为 $v_i\to u{\Rightarrow }^{\ast }{v}_j{\to }^{\ast }{v}_i$，那么 $L,R,B$ 中大于 $v_i$ 的部分可以删除（因为和环 $c$ 没有关系）。对于那些 $v_j<v_k<v_i$ 的部分，可能在递归处理时被放到新环的不同侧，但最终必须位于 $c$ 的同一侧，因此我们需要把它们都移动到同一侧并合并对应的 block。若无法移动到同一侧表明 $G$ 不是平面图。

复杂度分析

具体的实现除了一开始预处理的一次 $dfs$ 外，只需要一个 $dfs$ 函数就能够完成所有工作。若在排序的时候使用桶排序等 $O(V)$ 的排序，就可以做到 $O(V)$ 的时间和空间复杂度。

代码

int stack[MAXN]; //the memory pool for linked list L,R, store id of vertices
int _n[MAXN],next = _n + 1;  /*the successor pointer for linked list L,R, 
store index of array stack, next[0] represents end of list L, 
next[-1] represents the end of list R*/
int path[MAXN]; //path[x] denotes id of the path of x
int f[MAXN];   //f[i] represents end vertex of the i-th path 
stack<pair<int,int>> B; /*store the start pointer(index of array stack)
of each block, 0 for empty*/
int s, p;

void pathfinder(int v) {
  for (int w : G[v]) {
    if (dfn[v] < dfn[w]) {
      if (s == 0) s = v, p++;
      path[w] = p; pathfinder(w);

      //(1) delete all the vertices in L,R,B that >= v
      while (true) { //delete vertices in B
        int x = B.top().first, y = B.top().second;
        if ((stack[x] >= v || x == 0) && (stack[y] >= v || y == 0))
          B.pop();
        else break;
      }
      int x = B.top().first, y = B.top().second;
      if (stack[x] >= v) B.top().first  = 0;
      if (stack[y] >= v) B.top().second = 0;
      while (next[-1] != 0 && stack[next[-1]] >= v) //delete vertices in R
        next[-1] = next[next[-1]];
      while (next[0] != 0 && stack[next[0]] >= v) //delete vertices in L
        next[0] = next[next[0]];

      
      if (path[w] != path[v]) {
        /*(2) all of segment with first edge (v, w) has been embedded. 
        New blocks must be moved from inside to outside and merge with 
        the block of outmost path to form the whole segment*/

        int L0 = 0; //we need to move all the new paths in R (v > f[path[w]]) to L
        while (stack[next[-1]] != 0) {
          int x = B.top().first, y = B.top().second;
          if (stack[x] <= f[path[w]] && stack[y] <= f[path[w]]) break;
          if (stack[x] > f[path[w]]) {
            if (stack[y] > f[path[w]]) planar = false;
            L0 = x;
          } else { //stack[y] > f[path[w]]
            int tmp = next[L0];
            next[L0] = next[-1]; next[-1] = next[y]; next[y] = tmp;
            L0 = y;
          }
          B.pop();
        }
        int x = B.top().first, y = B.top().second;
        B.pop(); //delete the block of the outmost path and merge a new one
        if (x != 0) B.push(make_pair(x, y));
        else if (L0 != 0 || y != 0) B.push(make_pair(L0, y));
        next[-1] = next[next[-1]]; //delete end-of-stack marker on stack R
      }
    } else { //v->w is frond, current path complete
      if (s == 0) s = v, p++;
      f[p] = w;
      //(3) switch blocks of entries from inside to outside to embed p inside
      int L0 = 0, R0 = -1;
      while ((next[L0] != 0 && stack[next[L0]] > w) || (next[R0] != 0 && stack[next[R0]] > w)) {
        int x = B.top().first, y = B.top().second;
        if (x != 0 && y != 0) {
          if (stack[next[L0]] > w) {
            if (stack[next[R0]] > w) planar = false;
            swap(next[L0], next[R0]);
            swap(next[x], next[y]);
            L0 = y, R0 = x;
          } else { //stack[next[R0]] > w
            L0 = x, R0 = y;
          }
        } else if (x != 0) {
          int tmp = next[x];
          next[x] = next[R0];
          next[R0] = next[L0];
          next[L0] = tmp;
          R0 = x;
        } else if (y != 0)
          R0 = y;
        B.pop();
      }
      /*(4) add w to stack L, add a new block merged from p and removed blocks
      if segment containing current path is not a single frond, add an 
      end-of-stack marker to stack R
      */
      //Add w to stack L
      if (f[path[s]] < w) {
        ++tot;
        if (L0 == 0) L0 = tot;
        stack[tot] = w;
        next[free] = next[0];
        next[0] = free;
      }
      //Add the new block merged from p and the removed blocks
      if (R0 == -1) R0 = 0;
      if (L0 != 0 || R0 != 0 || v != s)
        B.push(make_pair(L0, R0));
      /*If segment containing current path is not a single frond, 
      add an end-of-stack marker to right stack*/
      if (v != s) {
        ++tot;
        stack[free] = 0;
        next[tot] = next[-1];
        next[-1] = tot;
      }

      s = 0;
    }
  }
}

s = 1, p = 1; 
path[1] = 1; 
pathfinder(1); //start from vertex 1

参考资料：知乎——线性平面图判定