TY - JOUR
T1 - Embedding Sun Graphs in a Single Page
AU - Banukumar, Mahavir
JF - The Bulletin of Society for Mathematical Services and Standards
VL - 5
SP - 31
EP - 36
SN - 2277-8020
PY - 2013
PB - SciPress Ltd
DO - 10.18052/www.scipress.com/BSMaSS.5.31
UR - https://www.scipress.com/BSMaSS.5.31
KW - Book Embedding
KW - Book Thickness
KW - Page Number
KW - VLSI Design
AB - A book consists of a line in the 3-dimensional space, called the spine, and a number of pages, each a half-plane with the spine as boundary. A book embedding (p, r) of a graph consists of a linear ordering of p, of vertices, called the spine ordering, along the spine of a book and an assignment r, of edges to pages so that edges assigned to the same page can be drawn on that page without crossing. That is, we cannot find vertices u, v, x, y with p(u) < p(x) < p(v) < p(y), yet the edges uv and xy are assigned to the same page, that is r(uv) = r(xy). The book thickness or page number of a graph G is the minimum number of pages in required to embed G in a book. In this paper we consider the Sun Graph or the Trampoline graph and obtain the printing cycle for embedding the Sun Graph in a single page. We also give a linear time algorithm for such an embedding.
ER -