The matching book embeddings of pseudo-Halin graphs

Zeling Shao, Yanling Hu, Huiru Geng, Zhiguo Li


The book embedding of a graph G is to arrange the set of points of the graph on a line (spine) and embed the edges on the half-plane bounded by the spine so that the edges in the same page do not intersect with each other. If the maximum degree of vertices in each page is 1, the book embedding is matching book embedding. The matching book thickness of G is the minimum number n that G can be matching book embedded in n-page. In this paper, the matching book thickness of pseudo-Halin graphs is determined.


book embedding, matching book embedding, matching book thickness, pseudo-Halin graph

Full Text:




F. Bernhart, P. C. Kainen, The book thickness of a graph, J. Combin. Theory Ser. B, 27 (1979), 320–331.

P. C. Kainen, Complexity of products of even cycles, Bull. Inst. Combin. Appl., 62 (2011), 95–102.

S. Overbay, Generalized book embeddings, Fort Collins: Colorado State University Ph.D Thesis, 1998.

B. Zhao, Y Tian and J Meng, Embedding semistrong product of paths and cycles in books, J. Nat. Sci. Hunan Norm. University, 38 (6) (2015), 73–77.

Z. L. Shao, X. L. Hao and Z. G. Li, The book embedding of Schrijver graph, Utilitas Mathematica, 107 (2018), 157–165.

X. L. Li, Book embedding of graphs, ZhengZhou: ZhengZhou University, 2002.

J. Yang, Z. L. Shao and Z. G. Li, Embedding cartesian product of some graphs in books, Commun. Math. Res., 34 (03) (2018), 253–260.

H. Enomoto, T. Nakamigawa T and K. Ota, On the pagenumber of complete bipartite graphs, J. Combin. Theory Ser. B, 71 (1997), 111–120.

P. C. Kainen, S Joslin and S. Overbay, On dispersability of some circulant graphs, arXiv preprint arXiv:2109.10163.

P. C. Kainen, S. Overbay, Cubic planar bipartite graphs are dispersable, arXiv preprint arXiv:2107.04728.

S. S. Joslin, P. C. Kainen and S. Overbay, On dispersability of some products of cycles, Missouri Journal of Mathematical Sciences, 33 (2) (2021): 206–213.

Z. L. Shao, H. R. Geng and Z. G. Li, Matching book thickness of generalized Petersen graphs, Electron. J. Graph Theory Appl., 10 (1) (2022), 173–180.

Z. L. Shao, Y. Q. Liu and Z. G. Li, Bipartite cubic planar graphs are dispersable, arXiv preprint arXiv:2107.00907.

Z. L. Shao, Y. Q. Liu and Z. G. Li, Matching book embedding of the cartesian product of a complete graph and a cycle, Ars Combinatoria, 153 (2020), 89–97.

L. Z. Liu, Z. F. Zhang, On the structure properties and chromatics of pseudo Halin graphs, J. Lanzhou Railway University, 20 (04) (2001), 105–107.

F. R. K. Chung, F. T. Leighton and A. L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM J. Algebraic Discrete Method, 8 (1) (1987), 33–58.


  • There are currently no refbacks.

ISSN: 2338-2287

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

View EJGTA Stats