圖形的書式嵌入之研究

Abstract

一本書是一個由若干個共同相交於一共同邊界 (稱為書脊) 之半平面 (稱為書頁) 所成的集合；一個無指向性圖形之書式嵌入則由以下所述兩件事所組成：(i) 圖形的所有點依某順序一字陳列在書脊上，(ii) 將圖形的所有邊分配繪至某書頁中，並滿足繪至同一書頁的邊並不交錯。 圖形G可以書式嵌入的最小頁數稱之為圖形G的頁數，p(G)；另外，一頁的寬度定義為任一垂直書脊的直線在此頁中跨越的最大邊數，而一書式嵌入的寬度w(G)為頁寬度中的最大數。 在書式嵌入的研究中，主要的目標是求一個圖形的書式嵌入所使用的總頁數最少，或是使得最大的頁寬度越小越好，還有越少越好的點的相異型式。 在本篇論文中，第二章主要著眼於樹狀圖，X樹狀圖，完全圖及k層的Kn圓柱圖C(k,n)四種圖形的最少使用頁數與最大頁寬度之研究；最後，第三章中討論了格子圖與樹狀圖的型式數。

A book is a set of half-planes (the pages of the book) that share a common boundary line (the spine of the book). An embedding of a simple undirected graph of G (a pair of vertices are connected by at most one edge) in a book consists of an ordering of the vertices of G along the spine (horizontal line) of the book, together with an assignment of each edge of G to a page of the book, in which edges assigned to the same page do not cross. The minimum number of pages in which a graph G can be embedded is its pagenumber, p(G). And the width of a page is the maximum number of edges that cross any line perpendicular to the spine of the book. The width of a book embedding, w(G), is the maximum width of any page of the book. In devising an embedding, One strives to minimize both the number of pages used, the maximum width of any page and the number of different types. In this thesis, the main results in Chapter 2 focus on the pagenumber and the pagewidth of trees, X-trees, complete graphs and the k-depth Kn-cylinder C(k,n). Then, in Chapter 3 we study the typenumber of lattice graphs and trees.