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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy, J. A. and Murty, U. S. R., Graph Theory with Application, Macmillan, London, 1976.
Bilski, T., Optimum embedding of complete graphs in books, Discrete Math., 182, 1998, 21–28.
Chung, F. R. K., Leighton, F. T. and Rosenberg, A. L., Embedding graph in books: A layout problem with applications to VLSI design, SIAM J. Algebr. Discrete Methods, 8(1), 1987, 33–58.
Endo, T., The page number of toroidal graphs is at most seven, Discrete Math., 175, 1997, 87–96.
Nakamoto, A. and Ozeki, K., Book embedding of toroidal bipartite graphs, SIAM J. Discrete Math., 26 (2), 2012, 661–669.
Fang, J. F. and Lai, K. C., Embedding the incomplete hypercube in books, Inf. Process. Lett., 96, 2005, 1–6.
Enomoto, H., Nakamigawa, T. and Ota, K., On the page number of complete bipartite graphs, J. Comb. Theory B, 71, 1997, 111–120.
Sperfeld, K., On the page number of complete odd-partite graphs, Discrete Math., 313, 2013, 1689–1696.
Swaminathan, R., Giraraj, D. and Bhatia, D. K., The page number of the class of bandwidth-k graphs is k - 1, Inf. Process. Lett., 55, 1995, 71–74.
Yang, W. H. and Meng, J. X., Embedding connected double-loop networks with even cardinality in books, Appl. Math. Lett., 22, 2009, 1458–1461.
Garey, M. R., Johnson, D. S., Miller, G. L. and Papadimitrion, C. H., The complexity of coloring circular arcs and chords, SIAM J. Algebr. Discrete Methods, 1(2), 1980, 216–217.
Kapoor, N., Russell, M., Stojmenovic, I. and Zomaya, A. Y., A genetic algorithm for finding the page number of interconnection networks, JPDC, 62, 2002, 267–283.
Shahrokhi, F. and Shi, W., On crossing sets, disjiont sets and page number, J. Algorithms, 34, 2000, 40–53.
Wood, D. R., Degree constrained book embeddings, J. Algorithms, 45, 2002, 144–154.
Watkins, M. E., A theorem on Tait colorings with an application to generalized Petersen graphs, J. Comb. Theory, 6, 1969, 152–164.
Bemhart, F. and Kainen, B., The book thickness of a graph. J. Comb. Theory B, 27, 1979, 320–331.
Yannakakis, M., Embedding planar graph in four pages. J. Comput. Syst. Sci., 38, 1989, 36–37.
Ollmann, L. T., On the book thicknesses of various graphs, in Hoffman, F., Levow, R. B. and Thomas, R. S. D., editors, Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. VIII of Congr. Numer., Utilitas Math., 1973.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Natural Science Foundation of China (Nos. 11531010, 11401510, 11501487), the Key Laboratory Project of Xinjiang (No. 2015KL019) and the Doctoral Fund of Xinjiang University (No.BS150208).
Rights and permissions
About this article
Cite this article
Zhao, B., Xiong, W., Tian, Y. et al. Embedding generalized Petersen graph in books. Chin. Ann. Math. Ser. B 37, 385–394 (2016). https://doi.org/10.1007/s11401-016-1010-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11401-016-1010-4