# A simple equality for book embedding of two graphs

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 the minimum number of pages in which the graph $$G$$ can be embedded.

Recently, I wondered whether the following result is right:

Let $${G}$$ be a simple connected graph, a graph $${G'}$$ is from the graph $$G$$ by adding a new vertex on any edge $$e$$ of $$G$$, then $$bt( {G'})=bt(G).$$

I will appreciate it if someone could give any suggestions.

• I don't think so. Every graph can be embedded into a book with 3 pages (but an edge may pass from page to page indefinitely). If your claim were true, the page number of any graph would be at most 3. – Ilya Bogdanov Nov 21 '19 at 20:05

The answer is "no", since every graph has a subdivision that is embeddable in 3 pages (as stated in Bogdanov's answer). For example, the graph obtained from a complete graph $$K_n$$ by subdividing each edge $$O(\log n)$$ times has a 3-page book embedding. On the other hand, it is conjectured that there is a function $$f$$ such that for every graph $$G$$, if $$G^\prime$$ is the graph obtained from $$G$$ by subdividing each edge exactly once, then $$\text{bt}(G) \leq f( \text{bt} (G^\prime) )$$. This conjecture is due to Blankenship and Oporowski. See the following paper for a full discussion: V. Dujmovic and D.R. Wood. "Stacks, queues and tracks: Layouts of graph subdivisions", Discrete Math. & Theoretical Comput. Sci. 7:155–202, 2005.
• @Bogdanov@User26635 Yes，good job. I also had this conjecture for complete graph $K_n$: For a complete graph $K_n$, if $K'_n$ is the graph obtained from $K_n$ by subdividing each edge at most once, Then $bt(K_n)=bt(K'_n)$. Thank you for telling me the reference. – Jacob.Z.Lee Nov 24 '19 at 1:53