On Dispersable Book Embeddings
share
In a dispersable book embedding, the vertices of a given graph G must be ordered along a line l, called spine, and the edges of G must be drawn at different half-planes bounded by l, called pages of the book, such that: (i) no two edges of the same page cross, and (ii) the graphs induced by the edges of each page are 1-regular. The minimum number of pages needed by any dispersable book embedding of G is referred to as the dispersable book thickness dbt(G) of G. Graph G is called dispersable if dbt(G) = Δ(G) holds (note that Δ(G) ≤ dbt(G) always holds). Back in 1979, Bernhart and Kainen conjectured that any k-regular bipartite graph G is dispersable, i.e., dbt(G)=k. In this paper, we disprove this conjecture for the cases k=3 (with a computer-aided proof), and k=4 (with a purely combinatorial proof). In particular, we show that the Gray graph, which is 3-regular and bipartite, has dispersable book thickness four, while the Folkman graph, which is 4-regular and bipartite, has dispersable book thickness five. On the positive side, we prove that 3-connected 3-regular bipartite planar graphs are dispersable, and conjecture that this property holds, even if 3-connectivity is relaxed.
READ FULL TEXT