第四章 平面图（ planar graph） 4.1 平面图的基本概念 4.1.1 平面图及平面嵌入 在一张纸上画图的图解时常常会发现，不仅需要允许各条边在结点上相交，而且 还允许各条边在某些点上相交。这样的点称为交叉点；而相交的边，说成是相互交叉 的边。 例 4.1 在图 4.1(a) 中，给出了一个无向图，其中有三个交叉：边 (v 1,v 4)和边 (v 2,v 3)交 叉；边 (v 1,v 5)和边 (v 2,v 3)交叉；边 (v 1,v 5)和边 (v 3,v 4)交叉。 (a) (b) 图 4.1 平面图 定义 4.1 设图 G=<V,E>是一个无向图， 如果能够把 G的所有结点和边画在平面上， 且使得 任何两条边除此了端点外没有其他的交点，就称 G是一个 平面图（ planar graph ）。或称 G 可嵌入平面 S。若 G可嵌入平面，则称 G是可平面图 。画出的无边相