Embedding generalized Petersen graph in books

Abstract

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.

Keywords

Book embedding / Page number / Generalized Petersen graph

References

[1] Bondy J. A., Murty U. S. R.. Graph Theory with Application, 1976, London: Macmillan

[2] Bilski T.. Optimum embedding of complete graphs in books. Discrete Math., 1998, 182: 21-28

[3] Chung F. R. K., Leighton F. T., Rosenberg A. L.. Embedding graph in books: A layout problem with applications to VLSI design. SIAM J. Algebr. Discrete Methods, 1987, 8(1): 33-58

[4] Endo T.. The page number of toroidal graphs is at most seven. Discrete Math., 1997, 175: 87-96

[5] Nakamoto A., Ozeki K.. Book embedding of toroidal bipartite graphs. SIAM J. Discrete Math., 2012, 26(2): 661-669

[6] Fang J. F., Lai K. C.. Embedding the incomplete hypercube in books. Inf. Process. Lett., 2005, 96: 1-6

[7] Enomoto H., Nakamigawa T., Ota K.. On the page number of complete bipartite graphs. J. Comb. Theory B, 1997, 71: 111-120

[8] Sperfeld K.. On the page number of complete odd-partite graphs. Discrete Math., 2013, 313: 1689-1696

[9] Swaminathan R., Giraraj D., Bhatia D. K.. The page number of the class of bandwidth-k graphs is k - 1. Inf. Process. Lett., 1995, 55: 71-74

[10] Yang W. H., Meng J. X.. Embedding connected double-loop networks with even cardinality in books. Appl. Math. Lett., 2009, 22: 1458-1461

[11] Garey M. R., Johnson D. S., Miller G. L., Papadimitrion C. H.. The complexity of coloring circular arcs and chords. SIAM J. Algebr. Discrete Methods, 1980, 1(2): 216-217

[12] Kapoor N., Russell M., Stojmenovic I., Zomaya A. Y.. A genetic algorithm for finding the page number of interconnection networks. JPDC, 2002, 62: 267-283

[13] Shahrokhi F., Shi W.. On crossing sets. disjiont sets and page number, J. Algorithms, 2000, 34: 40-53

[14] Wood D. R.. Degree constrained book embeddings. J. Algorithms, 2002, 45: 144-154

[15] Watkins M. E.. A theorem on Tait colorings with an application to generalized Petersen graphs. J. Comb. Theory, 1969, 6: 152-164

[16] Bemhart F., Kainen B.. The book thickness of a graph. J. Comb. Theory B, 1979, 27: 320-331

[17] Yannakakis M.. Embedding planar graph in four pages. J. Comput. Syst. Sci., 1989, 38: 36-37

[18] Ollmann L. T.. Hoffman F., Levow R. B., Thomas R. S. D.. On the book thicknesses of various graphs. Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1973