补充两个平面图的性质：
一.设原图有\(C\)个连通块，则\(V-E+F=C+1\)
二.对于一个简单（无重边无自环）连通平面图，若\(V≥3\)，则\(E\leq 3V-6\)
证：由于无重边无自环，所以一个面的边界至少有三条边（最外面的无穷面的边界定义为将其与非无穷面分隔开的边），而一条边挨着两个面，故有\(2E≥3F\)，代入欧拉公式即可
来考虑这道题目，将所有点按照哈密顿回路排序之后，不难知道如果存在两条边\((i,j),(p,q)(i<j,p<q)\)满足\(i<p<j<q\)或者\(p<i<q<j\)则这两条边不能同时在环的内部或者外部（其实这个是必要条件，如果最开始不按照哈密顿环排序，是不是可能存在一种平面图的放置方式呢，这个没办法证明，只能按照应试的技巧来做），于是这就是一个2-SAT问题了（利用上面性质二可以将时间复杂度优化到\(O(n^2)\)）；当然实际上这里的条件都是充要的，所以其实可以按照并查集来做
标签：连通,平面图,自环,无穷,平面,无重边 From： https://www.cnblogs.com/dingxingdi/p/18369817