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

Upper-embedding of a near-triangulation graph

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

In this paper, we consider upper-embedding of near-triangulation graphs,where near-triangulation plane graph is a plane graph whose facial cycles are 3-cycle except one. Kundu show that if the geometric dual G^＊ of a near-triangulation plane graph G contains a set of [1/2φ] independent edges ,then the maximum genus γM （G）of G is at least[β（G）/2]-1.In this paper we conclude one kind of near-triangulation graphs without G0 is upper-embedding.