一类近三角剖分图的上可嵌入性

摘要

一个图在某个曲面上的嵌入三角剖分该曲面,那么这个图是上可嵌入的,对于一个近三角剖分图却不一定是上可嵌入的。已经证明了平面近三角剖分图的上可嵌入性与独立边集之间的关系是:若G的对偶图G*有[1/2φ]个独立边集,那么图G的最大亏格γM(G)=[β(G)2]-1。进一步讨论了平面近三角剖面图G有k个三角Δ1,Δ2,,Δk其上可嵌入的条件。