Skip to main content

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$K_n$ by subdividing each edge O(log n)$O(\log n)$ times has a 3-page book embedding. On the other hand, it is conjectured that there is a function f$f$ such that for every graph G$G$, if G'$G^\prime$ is the graph obtained from G$G$ by subdividing each edge exactly once, then bt(G) <= f( bt(G') )$\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.

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' is the graph obtained from G by subdividing each edge exactly once, then bt(G) <= f( bt(G') ). 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.

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.

Source Link

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' is the graph obtained from G by subdividing each edge exactly once, then bt(G) <= f( bt(G') ). 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.