Book Embedding of Infinite Family of Semi-periodic Graphs with Average Degree Between 4 and 5

Benny Pinontoan; Jullia Titaley; Chriestie Montolalu

doi:10.35799/jis.v26i2.69627

Authors

Benny Pinontoan Department of Mathematics Sam Ratulangi University, Manado, Indonesia https://orcid.org/0000-0002-3130-0159
Jullia Titaley Department of Mathematics Sam Ratulangi University, Manado, Indonesia https://orcid.org/0009-0000-9014-4208
Chriestie Montolalu Department of Mathematics Sam Ratulangi University, Manado, Indonesia https://orcid.org/0009-0004-6972-1428

DOI:

https://doi.org/10.35799/jis.v26i2.69627

Keywords:

Book embedding, pagenumber, tile

Abstract

We construct an infinite sequence of semi-periodic graphs, namely by gluing some identical pieces in a circular fashion, with average degree between 4 and 5. We do book embedding of these graphs by putting the vertices on the spine of a book and the edges on 3 pages of the book without crossing, that is, with pagenumber 3.

References

Alam, J.M., Bekos, M.A., Gronemann, M., & Kaufmann, M. (2025). The page number of monotone directed acyclic outerplanar graphs is four or five. Leibniz International Proceedings in Informatics (LIPIcs), 357(9), 1–9. https://doi.org/https://doi.org/10.4230/LIPIcs.GD.2025.9

Bekos, M.A., Da Lozzo, G., Griesbach, S.M., Gronemann, M., Montecchiani, F., & Raftopoulou, C. (2024). Book embeddings of k-framed graphs and k-map graphs. Discrete Mathematics, 347(1), 113690. https://doi.org/10.1016/j.disc.2023.113690

Chaplick, S., Förster, H., Hoffmann, M., & Kaufmann, M. (2026). Monotone Arc Diagrams with few Biarcs. Journal of Graph Algorithms and Applications, 29(3), 111–142. https://doi.org/10.7155/jgaa.v29i3.3006

Chung, F.R.K., Leighton, F.T., & Rosenberg, A.L. (1987). Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design. SIAM Journal on Algebraic Discrete Methods, 8(1), 33–58. https://doi.org/10.1137/0608002

Da Lozzo, G., Frati, F., & Rutter, I. (2026). Upward Book Embeddings of Partitioned Digraphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), 367, pp. 36:1-36:18. https://doi.org/10.4230/LIPIcs.SoCG.2026.36

Dehghan, A., Siuta, K., Skorupka, A., Betlen, A., Miller, D., Kamiński, B., & Prałat, P. (2024). Unsupervised framework for evaluating and explaining structural node embeddings of graphs. Journal of Complex Networks, 12(2), cnae003. https://doi.org/10.1093/comnet/cnae003

Depian, T., Fink, S.D., Ganian, R., & Nöllenburg, M. (2026). The Parameterized Complexity Of Extending Stack Layouts. Journal of Graph Algorithms and Applications, 29(3), 39–78. https://doi.org/10.7155/jgaa.v29i3.3221

Kainen, P. C., Joslin, S., & Overbay, S. (2024). On Dispersability of Some Circulant Graphs. Journal of Graph Algorithms and Applications, 28(1), 225–241. https://doi.org/10.7155/jgaa.v28i1.2941

Pinontoan, B., & Richter, R. . (2003). Crossing numbers of sequences of graphs II: planar tiles. Journal of Graph Theory, 42, 332–341. https://doi.org/10.1002/jgt.10097

Pinontoan, B., & Titaley, J. (2019). Book Embeddings of Infinite Sequences of Extended Periodic Regular Graphs. IOP Conf. Ser.: Mater. Sci. Eng, 567, 012011.

Pinontoan, B., Titaley, J., & Montolalu, C. E. J. . (2019). Book embedding of 3- crossing-critical graphs with rational average degree between 3.5 and 4. IOP Conf. Ser.: Mater. Sci. Eng, 567, 012016.

Pinontoan, B., Titalley, J., & Weku, W. C. (2023). Book embedding of infinite family of almost-planar crossing-critical graphs. AIP Conf. Proc., 2694, 080013. https://doi.org/10.1063/5.0118319

Richter, R. B., & Thomassen, C. (1993). Minimal Graphs with Crossing Number at Least k. Journal of Combinatorial Theory, Series B, 58(2), 217–224. https://doi.org/10.1006/jctb.1993.1038

Shao, Z., Yao, M., & Li, Z. (2026). The matching book embedding under some graph operations. Electronic Journal of Graph Theory and Applications, 14(1), 205–214. https://doi.org/10.5614/ejgta.2026.14.1.13

Zheng, Y., Yi, L., & Wei, Z. (2025). A survey of dynamic graph neural networks. Frontiers of Computer Science, 19(6), 196323. https://doi.org/10.1007/s11704-024-3853-2