5
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hung Le
    May 4, 2015 at 18:19
  • $\begingroup$ I also updated the question so that it clearer. $\endgroup$
    – Hung Le
    May 4, 2015 at 18:24
  • $\begingroup$ @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? $\endgroup$
    – Saeed
    May 5, 2015 at 8:24
  • $\begingroup$ 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. $\endgroup$
    – Hung Le
    May 5, 2015 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.