Page Number and Graph Treewidth

Page Number and Graph Treewidth

Li Xianglu (Zhongyuan University of Technology, China)
Copyright: © 2010 |Pages: 6
DOI: 10.4018/jamc.2010070104

Abstract

Book-embedding of graph G involves embedding its vertices along the spine of the book and assigning its edges to pages of the book such that no two edges cross on the same page. The pagenumber of G is the minimum number of pages in a book-embedding of G. In this paper, the authors also examine the treewidth TW(G), which is the minimum k such that G is a subgraph of a k-tree. The authors then study the relationship between pagenumber and treewidth. Results show that PN(G)=TW(G), which proves a conjecture of Ganley and Heath showing that some known upper bounds for the pagenumber can be improved.
Article Preview
Top

Introduction

The book-embedding problem for graph jamc.2010070104.m01 is to embed its vertices onto a line along the spine of the book and to draw the edges on pages of the book such that no two edges on the same page cross, and the number of used pages is minimized.

The book-embedding problem has been motivated by several areas of computer science such as VLSL theory, multilayer printed circuit boards (PCB), sorting with parallel stacks and Turning-machine and the design of fault-tolerant processor arrays, etc (e.g., Chung et al., 1987). The DIOGENES approach to fault-tolerant processor arrays, proposed by Rosenberg (1986), is the most famous one. In the DIOGENES approach, the processing elements are laid out in a logical line, and some number of bundles of wires run in parallel with the line. The faulty elements are bypassed, and the fault-free ones are interconnected through the bundles. Here, the bundles work as queues and/or stacks. If the bundles work as stacks, then the realization of an interconnection network needs a book-embedding of the interconnection network. In this case, the number of pages corresponds to the number of bundles of the DIOGENES stack layout. Therefore, book-embeddings with few pages realize more hardware-efficient DIOGENES stacks layouts.

The book-embedding problem can be stated as a graph-labeling problem as follows. We shall follow the graph-theoretic terminology and notation used by Bondy and Murty (1976) and Golumbic (1980).

Given a simple connected graph jamc.2010070104.m02 with jamc.2010070104.m03 vertices, a bijection f:jamc.2010070104.m04is called a labeling of jamc.2010070104.m05 by Chung(1988), where jamc.2010070104.m06 represents the label of vertex jamc.2010070104.m07 Let jamc.2010070104.m08be the vertex with label jamc.2010070104.m09 Then the labeling f can also be regarded as an ordering jamc.2010070104.m10 on a line. For a labeling f, two edges jamc.2010070104.m11 are said to be crossing if jamc.2010070104.m12 or jamc.2010070104.m13.

With respect to a labelingjamc.2010070104.m14, a partition jamc.2010070104.m15 of the edge set jamc.2010070104.m16 is called a page partition if no two edges in any subset jamc.2010070104.m17 are crossing. This page partition can be thought of as a coloring of jamc.2010070104.m18 where the edges in jamc.2010070104.m19 have color jamc.2010070104.m20and no two edges of the same color are crossing. Thus, a page partition jamc.2010070104.m21 represents an assignment of edges of jamc.2010070104.m22 to pages of the book. We call the minimum number of subsets in a page partition jamc.2010070104.m23 the page number of jamc.2010070104.m24 under labeling jamc.2010070104.m25, and denote it byjamc.2010070104.m26. The pagenumber of jamc.2010070104.m27 is then defined as

jamc.2010070104.m28
where jamc.2010070104.m29 is taken over all labelings of jamc.2010070104.m30.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing