摘要
一个图在某个曲面上的嵌入三角剖分该曲面,那么这个图是上可嵌入的,对于一个近三角剖分图却不一定是上可嵌入的。已经证明了平面近三角剖分图的上可嵌入性与独立边集之间的关系是:若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.
出处
《齐齐哈尔大学学报（自然科学版）》
2008年第4期69-71,共3页
Journal of Qiqihar University(Natural Science Edition)
基金
山东省自然科学基金资助(Q2007G02)
关键词
最大亏格
上可嵌入
近三角剖分
maximum genus
upper-embedding
near-triangulation
