【作者】 李湘露；

【导师】 林诒勋；

【作者基本信息】 郑州大学 ， 基础数学， 2002， 博士

【摘要】 本文研究无向简单有限图的书式嵌入问题。 书式嵌入的“书”是由一条书脊和多页书页构成。其中书脊为一条直线，书的每一页是由书脊所界定的半平面。给定图G的书式嵌入包括两部分内容：首先将G的顶点按照一个由线性标号所定义的顺序嵌入书脊上，其次将E（G）中的每条边分放于各页，使得每页中的边均可画在该页上而互不相交。 衡量图G书式嵌入优劣的指标有两个：书页数与页宽。相对于已知顶点嵌入方式的书页数定义为在该顶点嵌入方式下，使图G可嵌入的最少页数；而称在各种顶点嵌入方式下可嵌入图的书的最少页数为图G的书页数；每页的页宽则定义为每页中相交于书脊任意垂线的最多边数；图G在相对于给定顶点嵌入下的页宽定义为此嵌入下所有页宽的最大数；而图G的页宽为所有顶点嵌入方式下的最少页宽。 所谓图的书式嵌入问题即寻求以单个或两个指标为目标的最优嵌入。本文将以书页数为目标研究有关书式嵌入问题。 图的书式嵌入问题有多种定义方式，在本文中等价地定义为下述图的标号问题。 给定n个顶点的简单图G=（V，E），f为V→{1，2，…，n}的一一映射，任意f（v）∈{1，2，…，n}，称作顶点v的标号，若令u_i=f^-1（i），则f也可视为顶点在书脊上的线性顺序。任意两条边xy，uv∈E称为相交的当且仅当f（u）＜f（x）＜f（v）＜f（y）或者f（x）＜f（u）＜f（y）＜f（v）。对于给定的标号f，边集E的划分P＝（E₁，E₂，…，E_p）称为E（G）的页划分，如果每个子集E_i（1≤i≤p）中的任意两条边互不相交，此处的页划分可以作为边集E（G）的着色：对E_i的各边着色i，1≤i≤p。该着色满足；同色边不相交。在标号f下页划分的最小子集数称为图G关于f的书页数，记作PN（G，f）；则图G的书页数为： 其中／取遍 G的所有标号。此时对于任意整数k三 PNK)，称G为 可k页嵌入的。 图的书式嵌入起源于许多领域，包括：计算机科学，大型集成电路 （VLSI）理论，多层线路板印刷（PC旧s），平行机排序及Timing机图 等等。 该问题的难度相当大，即使对平面图而言判定其可否2页嵌人也是 NI3－完全的，并且甚至在给定顶点顺序的前提下，确定图的书页数也是 NP－完全的。由于该问题的难度较大，近年来许多学者致力于研究其多 项式可解的情形及上下界的确定。遗憾的是，到目前为止，仍未发现有 效算法。最近由J．L．Gaul时上．S．H。、atll研究了k树G的书页数问题，证明 了 k－树的书页数不超过人 ＋1，并提出了 PN闷)三人的猜想。 本文的主要研究内容包括以下四个方面；几类特殊图的书页数，书 页数与其它图论参数的关系，最优嵌入的一些性质，近似算法的设计。 主要结论如下： 1特殊图的书页数与最优嵌入 到目前为止，关于特殊图并没有太多精确的结果．关于笛卡尔乘积 图：凡XPn，Pn。XCn可两页嵌人的结论是作为定理卫．3的直接推论而 得到的。而对于强乘积及其它特殊图，却需要更多的技巧来确定其书页 数的上下界。本文得到如下精确结果： （1）对＊＊)卜L＊dder八八有｝。V（八＊）＝＊。 p)Petersen图的书页数为P州们＝3。 （3）路与路的强乘积尸，；十只；的书页数为 IZI)｝＝2。71 2 OO fil＝11＝3 PN厂＼①只。)＝｛ 3；J)＝3，if＞4 or ？n＝4，n＞4 I4 NL门＞5 叫路与圈的强乘积八。十＊；的书页数为 【3 Pi＝2 尸川几。十人门：二Z I。II)i＞3 ／ （5）圈与圈的强乘积 t‘；。4 C’；；。有 PN K。i CnCn)＝6． 2书页数与其它图论参数的关系 该文所讨论的图论参数为：树宽TI4”（G），路宽PWp)，带宽B（G）， 割宽C（G），循环带宽B。（（）；以硼环割宽C‘C（G）．下述结果证明并 推广了Ganley和Heath猜想。 阻）对于任意图G，有厂N、q三Tw(G广 （2）图的书页数，树宽，路宽，带宽的关系如下： ＊N（q＜T厂”厂）＜尸w(Q＜B(q． 仰图的书页数。树宽，路宽，割宽的关系如下。 ＊N（G）＜＊I4／?更多还原

【Abstract】 The problem of embedding graphs in books is studied in the dissertation.A book consists of a spine (which is just a line) and some number of pages (each of which is a half-plane with the spine as boundary). A book embedding of a graph G consists of placing the vertices of G on the spine in an order specified by a linear ordering of V’(G’) and assigning edges of the graph to pages so that edges assigned to the same page can be drawn on that page without crossing each other. There are two measures of 1 he quality of a book embedding of G. The first is the pagenumber of the embedding, which is the minimum number of pages in which graph G can be embedded; the second is the pagewidth. The width of a page is the maximum number of edges that intersect any half-line perpendicular to the spine in the page; the maximum width of any page is called the pagewidth with respect to the given embedding. Then the pagewidth of the graph G is the minimum pagewidth of any book embedding of G.The book embedding problem is to find good book embedding for a graph with respect to one or both of these measures. The dissertation focuses on the first measure to investigate the problem.The book embedding problem can be viewed in a variety of ways, and also stated as a graph-labeling problem as follows.Given a simple graph G-(V, E) with n vertices, a bijection f: V-{1,2.....n} is called a labeling of G. where f(v) {1. 2,.. ., n} representsthe label of vertex be the vertex with label . Then the labeling f can be also regarded as a linear ordering (u1,u2. .. ,un) on the spine of the book. Two edges in\.cy G E are said to be crossing if and only if f(u) < f(x) < f(v) < f(y) or f(x) < f(u) < f(y) < f(v). Under a labeling /, a partition P= (E1, E2,..., Ep) of edge set E(G) iscalled a page partition if no pair of edges in any subset Ei (1 < i < p) cross. This page partition can be regarded as a coloring of E(G) where the edges in Ei have color i and no crossing edges share the same color. Thus, a page partition P represents an assignment of edges of G to pages of the book. We call the minimum number of subsets of a page partition P the pagenumber of G under labeliny f, and denote it by PN(G,f). The pagenumber of G is then defined aswhere / is taken over all labelings of (V. G is said to be k page embecklable for any k > PN(G).The book embedding problem is interesting, because it arises from several areas of computer science, VLSI theory, multilayer printed circuit boards (PCB), sorting with parallel stacks and Turning-machine graph, etc.The problem is very difficult: it is NP-complete to decide whether a planar graph can be embedded in two pages, and even for a given labeling /, determining the pagenumber PN(G,f) is also NP-complete. So. most researchers now are interested in the polynomial solvable special cases and lower or upper bounds of the pagenumber. Up to now, most of the known upper bounds are asymptotic, and there is no polynomial approximation algorithm except, Cor planar graphs which have a 2-approximation algorithm. Recently. Ganley and Heath proved that PN(G) < k + 1 if G is a k.-tree, and they presented a conjecture that PN(G) < k for fc-trees.In the dissertation, the pagenumber and optimal embeddings of a variety of families of graphs are determined, including the strong product of G1 and G2: PnPm Pn Cm Cn Cm. Relations between pagenumber and other graph-theoretic parameters are established , such as treewidth,cyclic cutwidth. Finally, some properties of optimal book embedding of graphs are investigated and an approximation algorithm is presented for chordal graphs.The dissertation obtains results in four aspects as follows.1. Pagenumber of special graphsThere are not many exact results so far in this aspect. For the Cartesian products Pm x Pn<Pm x Cn. etc, the pagenumber 2 is a direct consequence of Theorem 1.3. However, the study of strong products Pm P Pn and others needs more techniques in determining upper and lower bounds. We obtain the following exact results.(1) For Mobi更多还原