Abstract
The concept of book embedding, originating in computer science, has found extensive applications in various problem domains. A book embedding of a graph G involves arranging the vertices of G in an order along a line and assigning the edges to one or more half-planes. The page number of a graph is the smallest possible number of half-planes for any book embedding of the graph. Determining the page number is a key aspect of book embedding and carries significant importance. This paper aims to investigate the non-trivial lower bound of the page number for both a graph G and a random graph \(G\in \mathcal {G}(n,p)\) by incorporating two seemingly unrelated concepts: edge-arboricity and Euler’s Formula. Our analysis reveals that for a graph G, which is not a path, \(pn(G)\ge \lceil \frac{1}{3} a_1(G)\rceil \), where \(a_1(G)\) denotes the edge-arboricity of G, and for an outerplanar graph, the lower bound is optimal. For \(G\in \mathcal {G}(n,p)\), \(pn(G)\ge \lceil \frac{1}{6}np(1-o(1))\rceil \) with high probability, as long as \(\frac{c}{n}\le p\le \frac{\root 2 \of {3(n-1)}}{n\log {n}}\).
Similar content being viewed by others
References
Even, S., Itai, A.: Queues, stacks, and graphs. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 71–86. Academic Press, New York (1971)
Tarjan, R.E.: Sorting using networks of queues and stacks. J. Assoc. Comput. Mach. 19, 341–346 (1972)
Rosenberg, A.L.: The Diogenes approach to testable fault-tolerant arrays of processors. IEEE Trans. Comput. C–32, 902–910 (1983)
Raghavan, R., Sahni, S.: Single row routing. IEEE Trans. Comput. C–32, 209–220 (1983)
Ollmann, L.T.: On the book thickness of various graphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, VIII, p. 459 (1973)
Bemhart, F., Kainen, B.: The book thickness of a graph. J. Comb. Theory Ser. B 27, 320–331 (1979)
Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Compariting queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5, 398–412 (1992)
Yannakakis, M.: Embedding planar graph in four pages. J. Comput. Syst. Sci. 38, 36–37 (1989)
Ento, T.: The pagenumber of toroidal graphs at most seven. Discrete Math. 175, 87–96 (1997)
Enomoto, H., Nakamigawa, T., Ota, K.: On the pagenumber of complete bipartite graphs. J. Comb. Theory Ser. B 71, 111–120 (1997)
Yang, J., Shao, Z.L., Li, Z.G.: Embedding cartesian product of some graphs in books. Commun. Math. Res. 34, 253–260 (2018)
Yang, W.H., Meng, J.X.: Embedding connected double-loop networks with even cardinality in books. Appl. Math. Lett. 22, 1458–1461 (2009)
Guan, X., Yang, W.: Embedding planar 5-graphs in three pages. Discrete Appl. Math. 282, 108–121 (2020)
Herrán, A., Colmenar, J.M., Duarte, A.: An efficient metaheuristic for the K-page crossing number minimization problem. Knowl. Based Syst. 207, 106352 (2020)
Nash-Williams, C.S.T.J.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 39, 12 (1964)
Erdös, P., Rényi, A.: On random graphs I. Pub. Math. Debrecen 6, 290–297 (1959)
Gibert, E.N.: Random graphs. Ann. Math. Stat. 30, 1141–1144 (1959)
Frieze, A., Karon’ski, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2016)
Acknowledgements
The authors would like to express their sincere gratitude to the anonymous reviewers for their valuable comments, constructive feedback, and insightful suggestions, which significantly improved the quality and clarity of this paper. Their efforts and contributions are greatly appreciated. The authors would also like to thank the handling editor for their expert guidance and support throughout the review process. Their meticulous attention to detail and valuable suggestions have been instrumental in shaping this manuscript.
Funding
Funding was provided by the Doctoral Scientific Research Foundation of Guizhou Medical University (Grant No. [2021]042), Guizhou Provincial Basic Research Program (Natural Science Category), Project ZK[2023]298, Science and Technology Program of Gansu Province of China No.21JR7RA511, NSFC No.32160151, No.12201268.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research is supported by the Doctoral Scientific Research Foundation of Guizhou Medical University [2021]042, Guizhou Provincial Basic Research Program (Natural Science Category), Project ZK[2023]298, Science and Technology Program of Gansu Province of China No. 21JR7RA511, NSFC No. 32160151, No. 12201268.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhao, B., Li, P., Meng, J. et al. Using Euler’s Formula to Find the Lower Bound of the Page Number. Graphs and Combinatorics 40, 44 (2024). https://doi.org/10.1007/s00373-024-02775-8
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-024-02775-8