Book Embedding Duality of Graphs

The definition of Book Embedding on Wikipedia: "A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. The vertices of the graph are required to lie on this boundary line, and the edges are required to stay within a single half-plane". Full definition is at (http://en.wikipedia.org/wiki/Book_embedding)

Planar embeddings have geometric duals, that has numerous algorithmic application. One of the very nice property of duality of planar graphs is that if $T$ is a spanning tree of a planar grpah $G$, then the set of edges not in $T$ in the dual is a spanning tree of the dual $G^*$. Is there any kind of similar geometric dual for book embeddings? Is there a similar property between the spanning tree of primal and dual graphs as in the planar case?

To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine edges are places where multiple cells meet so let's make them vertices as well.

Then, within each page of the book, the dual graph is a forest, with all vertices that are not adjacent to a leaf having degree three or more, and having the spine edge vertices as its leaves. So a book embedding with $p$ pages has a dual graph consisting of $p$ plane forests, sharing a common set of leaves in the same cyclic ordering as each other.

Whether this structure is useful for anything is a different question, of course.

As for your question about generalizations of planar graph decompositions into primal and dual spanning trees: I doubt something like that happens in book embeddings, but it can be generalized to embeddings of graphs onto non-planar manifolds. See my paper "Dynamic generators of topologically embedded graphs" (SODA'03).

I don't think we can get any property close to dual's properties in planar graphs, e.g Babai show that every graph can be embedded in a book with three pages (see Archdeacon's survey Theorem 5.1), so if $p$ is a duality property for books with three pages then $p$ holds for general graphs.

• I think the book embedding you mention is of different kind, that allows you to have vertices not on the spine of the book. The embedding in the definition I gave requires every vertex is on the same spine line, that is shared between pages. For this variant, the complete graph $K_n$ has page number $\lceil \frac{n}{2}\rceil$, not 3 as you mentioned. May 4 '15 at 18:19
• I also updated the question so that it clearer. May 4 '15 at 18:24
• @Hunglv, Yes your definition is different, I didn't read your definition so I didn't notice that you have other definition than the one Archdeacon uses in his survey. I'll leave this answer as is, which clarifies the other definition of book embedding. P.S: Anyway, whatever you wrote is from wiki, did you read anything related to book embedding except from wiki? May 5 '15 at 8:24
• Yes. I tried to, but not all. Most paper I read talk about how to embed a graph into a book and some special classes of graphs that have bounded page-numbers, none of the papers I read mentions some kind of duality. May 5 '15 at 15:18