2
$\begingroup$

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. enter image description here

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ilya Bogdanov
    Commented Nov 21, 2019 at 20:05

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$
    – Jacob.Z.Lee
    Commented Nov 24, 2019 at 1:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .