Book Embedding Of Graphs

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