K_(1,4)梯图的可定向嵌入亏格分布

本文主要运用刘彦佩提出的联树嵌入法研究一类新图-K_(1,4)梯图W_n的可定向嵌入亏格分布,并通过进一步递推化简,得到了K_(1,4)梯图在小亏格上的嵌入亏格多项式显式,以及在其他亏格上的简单递推式,使其在可定向亏格上的嵌入个数更容易地得出.     

顶点劈分与图的上可嵌入性（英文）

一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了[J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.     

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

完全二部图$K_{m,n}$的框架表示的唯一性

Kobayashi讨论了空间图在三维流形中的一类标准嵌入,给出了书册表示的概念,并证明了空间图$K_n$的书册表示的最少页是页变换与固边合痕意义下的不变量.本文给出了完全二部图$K_{m,n}$的框架表示的概念,并且证明了完全二部图的框架表示的最小层是层变换与固边合痕意义下的不变量.     

一个不可定向曲面的极小禁用子图的构造

曲面S的一个极小禁用子图是这样的一个图,它的任何一个顶点的度都不小于3,它不能嵌入在S上,但是删去任何一条边后得到的图能嵌入在S上.本文给出了四种构造一个不可定向曲面的极小禁用子图的方式,即粘合一个顶点,一个图的边被其它的图替换,粘合两个顶点,将一个图放在另一个图的一个曲面嵌入的面内.     

2-边连通3-正则非上可嵌入图的扩充（英文）

2-边连通3-正则图G是上可嵌入的当且仅当G可由图θ_1,θ_2或k_4通过一系列的M-或N-扩充得到(见[Acta Math.Appl.Sin.,Engl.Ser.,1998,14(4):337-346]).本文证明了若2-边连通3-正则图G是非上可嵌入的,则G可由图θ_3或双哑铃图通过一系列的M-或N-扩充得到.     

1-可嵌入曲面的图的边染色北大核心CSCD

一个图称为是1-可嵌入曲面的,当且仅当它可以画在一个曲面上,使得它的任何一条边最多交叉另外一条边.x′(G)和△(G)分别表示图G的边色数和最大度.给定图G是1-可嵌入到欧拉示性数x(∑)≥0的曲面∑上的图.如果△(G)≥8且不含4-圈或者△(G)≥7且围长g(G)≥4,则图G满足等式△(G)=x′(G),其中,g(G)表示图G中最短圈的长度.     

树环中的流量疏导问题研究

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的映射树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优映射使得G中任一边被H所有超边的映射经过的最大次数最小.应用超图嵌入圈(MCHEC)问题的算法可得超图嵌入树环问题的一个2-近似算法.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

A survey on book-embedding of planar graphs

The book-embedding problem arises in several area, such as very large scale integration (VLSI) design and routing multilayer printed circuit boards (PCBs). It can be used into various practical application fields. A book embedding of a graph G is an embedding of its vertices along the spine of a book, and an embedding of its edges to the pages such that edges embedded on the same page do not intersect. The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G. It is an important measure of the quality for book-embedding. It is NP-hard to research the pagenumber of book-embedding for a graph G. This paper summarizes the studies on the book-embedding of planar graphs in recent years.     

Embedding Generalized Petersen Graph in Books

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph $G$ can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.     

Pagenumber of complete bipartite graphs

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K_m,n) ? ?(m + 2n)/4?, which we conjecture optimal. We prove a result suggesting this is optimal for m ? 2n ? 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ?(7n ? 2)/9? pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

Minimal embeddings in the projective plane

We show that if G is a graph embedded on the projective plane in such a way that each noncontractible cycle intersects G at least n times and the embedding is minimal with respect to this property (i.e., the representativity of the embedding is n), then G can be reduced by a series of reduction operations to an n × n × n projective grid. The reduction operations consist of changing a triangle of G to a triad, changing a triad of G to a triangle, and several others. We also show that if every proper minor of the embedding has representativity < n (i.e., the embedding is minimal), then G can be obtained from an n × n × n projective grid by a series of the two reduction operations described above. Hence every minimal embedding has the same number of edges. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 153–163, 1997     

On the pagenumber of trivalent Cayley graphs

Book embedding of graphs is one of the graph layout problem. It is useful for the multiprocessor network layout or the fault-tolerant processor arrays. We show that the trivalent Cayley graphs proposed by Vadapalli and Srimani can be embedded in five pages, and show some additional results on cube-connected cycles.     

Grid Embedding of 4-Connected Plane Graphs

A straight line grid embedding of a plane graph G is a drawing of G such that the vertices are drawn at grid points and the edges are drawn as nonintersecting straight line segments. In this paper we show that if a 4-connected plane graph G has at least four vertices on its external face, then G can be embedded on a grid of size such that and , where n is the number of vertices of G. Such an embedding can be computed in linear time. Received March 30, 1995, and in revised form January 3, 1996.     

Minimal extensions of graphs to absolute retracts

A graph H is an absolute retract if for every isometric embedding h of, into a graph G an edge-preserving map g from G to H exists such that g · h is the identity map on H. A vertex v is embeddable in a graph G if G ? v is a retract of G. An absolute retract is uniquely determined by its set of embeddable vertices. We may regard this set as a metric space. We also prove that a graph (finite metric space with integral distance) can be isometrically embedded into only one smallest absolute retract (injective hull). All graphs in this paper are finite, connected, and without multiple edges.