关于图的相对嵌入研究

Roots of Topological Graph Theory lie in the famous Heawood Map Color Problem. Its applications have been discovered in extensive areas such as Topology, Algebra, Computer Science, Discrete Geometry and VLSI Layout, etc.. The relative embedding of graphs is an important research branch in Topological Graph Theory. By advancing the 2-Cell Embedding Theory to the relative embedding of graphs, this project focuses on studying the following aspects of relative embedding: calculating the relative maximum genus of complete graphs, complete bipartite graphs and other basic classes of graphs; determining the lower bound on relative maximum genus and the single-face relative embeddability of graphs; designing effective algorithms for relative maximum genus embedding of graphs; determining the relative genus of complete graphs, complete bipartite graphs and other basic classes of graphs; characterizing graphs which can be relative embedded in surfaces with small genus.

拓扑图论起源于著名的Heawood地图着色问题，其研究结果在拓扑学、代数学、计算科学、离散几何、VLSI布线等领域有重要的理论和应用意义。. 图的相对嵌入是拓扑图论领域的重要研究分支之一。本项目通过把图的2-胞腔嵌入理论发展到图的相对嵌入上来，主要研究相对嵌入的以下内容：计算完全图、完全二部图等基本图类的相对最大亏格；确定图的相对最大亏格下界与可单面相对嵌入性；设计图的相对最大亏格嵌入的有效算法；确定完全图、完全二部图等基本图类的相对亏格；刻画低亏格曲面上图的相对嵌入特征。

本项目以图在各种限制条件下的2-胞腔嵌入为研究对象。通过引入符号图的钻石积，确定了完全二部图K3,n的任意符号图的最小亏格的最大值，部分解决了Archdeacon提出的确定任意完全二部图的所有符号图的最小亏格的最大值问题。确定了非上可嵌入3-正则图均可由几类非上可嵌入3-正则图通过一系列的M-与N-扩充得到；利用刘彦佩教授提出的联树模型，给出了一类似Benzene结构图的亏格分布；研究了图在限定面边界条件下最大亏格的特征问题。