图的厚度与亏格

The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. The (orientable or nonorientable) genus of a graph is the minimum number k such that the graph can be embedded on the (orientable or nonorientable) surface of genus k. The thickness and genus of a graph are topological invariants of a graph, they are measurements of the non-planarity of a graph, and they also have important applications to VLSI design. Since the thickness problem is NP-hard and the genus problem is NP-complete, the results about thickness and genus are few. In this project, we will study the thicknesses and genera of graphs, plan to get the thicknesses of some special types of graphs and the (orientable and nonorientable) genera of some special types of graphs, improve the relation between the thickness and the orientable genus of a graph, and obtain the relation between the thickness and the nonorientable genus of a graph. The results that we will obtain is going to enrich the methods and theories in topological graph theory, and lay a solid foundation for practical applications.

图的厚度是指图的可平面子图分解中所含子图的最少个数．图的(可定向或不可定向)亏格是指图所能嵌入(可定向或不可定向)曲面的最小亏格．图的厚度和亏格作为图的拓扑不变量，是衡量图的不可平面性的重要指标，同时在超大规模集成电路的布局设计中也有重大的应用价值．但是由于图的厚度问题是NP-困难的，图的亏格问题是NP-完全的，目前国内外的已有结果并不多．本项目将以图的厚度和亏格为研究对象，拟得到一些特殊图类的厚度和(可定向和不可定向)亏格，改进图的厚度与可定向亏格间的关系，并得到图的厚度与不可定向亏格间的关系．这些结果的取得将会丰富拓扑图论的方法与理论，同时为实际应用打下坚实的基础．

本项目以图的厚度与亏格为研究对象，得到了一些完全多部图的厚度，图经过各种运算后新图的厚度，如点联合，边联合图的厚度，笛卡儿积图的厚度，联图的厚度等，以及一些完全三部图的四围长厚度。本项目的研究极大地丰富了厚度研究的结果与方法。