An Embedding Algorithm for a Specialcase of Extended Grids

Banukumar, Mahavir

doi:10.18052/www.scipress.com/BSMaSS.5.40

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

< Back to Volume

An Embedding Algorithm for a Specialcase of Extended Grids

Full Text 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:

https://doi.org/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:

March 2013

Authors:

Mahavir Banukumar

Keywords:

Book Embedding, Book Thickness, Page Number, VLSI Design

Export:

RIS, BibTeX, Text

Distribution:

Open Access

This work is licensed under a
Creative Commons Attribution 4.0 International License

References:

Bernhart, F. and Kainen, P.C., The book thickness of a graph. J. Combin. Theory Ser. B. v27. 320-331.

T. C. Biedl, T. Shermer, S. Wiitesided, S. Wismath, Bounds for orthogonal 3-Dgraph drawing, Journal of Graph Algorithms Appl. 3(1999) 63-79.

F. R. K. Chung , Frank Thomson Leighton , Arnold L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM Journalon Algebraic and Discrete Methods, v. 8 n. 1, pp.33-58, January 2, (1987).

F. R. K. Chung, F. T. Leighton, and A. L. Rosenbert, Diogenes - A methodology for designing fault-tolerant processor arrays, 13th International Conference of Fault-Tolerant Computing, 1983, pp.26-32.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, PHI, Second Edition, (2005).

Hasunuma, T., Embedding iterated line digraphs in books. Networks. v40. 51-62.

Hasunuma, T. , Yukio Shibata, Embedding de-Bruijn, Kautz and shuffle-exchange networks in books, Discrete Applied Mathematics, v. 78 n. 1-3, pp.103-116, Oct. 21, (1997).

Jywe-Fei Fang , Kuan-Chou Lai, Embedding the incomplete hypercube in books, Information Processing Letters, v. 96 n. 1, pp.1-6, 16 October (2005).

Konoe, M., Hagihara, K. and Tokura, N., On the pagenumber of hypercubes and cube-connected cycles. IEICE Trans. vJ71-D. 490-500.

Muder, D.J., Weaver, M.L. and West, D.B., Pagenumber of complete bipartite graphs. J. Graph Theory. v12. 469-489.

Opatrny, J., and Sotteau, D., Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Applied Mathematics 98 (2000) 237-254.

A. L. Rosenbert, The Diogenes approach to testable fault-tolerant arrays into processors, IEEE Trans. Comput., C-32 (1983), 902-910.

Show More Hide

Cited By:

This article has no citations.