Subscribe

Subscribe to our Newsletter and get informed about new publication regulary and special discounts for subscribers!

BSMaSS > Volume 5 > An Embedding Algorithm for a Specialcase of...
< Back to Volume

An Embedding Algorithm for a Specialcase of Extended Grids

Download PDF

Abstract:

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 (π,ρ) of a graph consists of a linear ordering of π, of vertices, called the spine ordering, along the spine of a book and an assignment ρ, 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 π(u) < π(x) < π(v) < π(y), yet the edges uv and xy are assigned to the same page, that is ρ(uv) = ρ(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 extended grid and prove that the 1xn extended grid can be embedded in two pages. We also give a linear time algorithm to embed the 1xn extended grid in two pages.

Info:

Periodical:
The Bulletin of Society for Mathematical Services and Standards (Volume 5)
Pages:
40-45
DOI:
10.18052/www.scipress.com/BSMaSS.5.40
Citation:
M. Banukumar "An Embedding Algorithm for a Specialcase of Extended Grids", The Bulletin of Society for Mathematical Services and Standards, Vol. 5, pp. 40-45, 2013
Online since:
Mar 2013
Export:
Distribution: