<p>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.</p>

<p>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.</p>

<p>Whether this structure is useful for anything is a different question, of course.</p>

<p>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 "<a href="http://arxiv.org/abs/cs.DS/0207082" rel="nofollow">Dynamic generators of topologically embedded graphs</a>" (SODA'03).</p>

CC BY-SA 3.0
2015-05-05T16:27:29.160Z
2015-05-05T16:27:29.160Z
David Eppstein
<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.1728" rel="nofollow">Archdeacon's survey</a> Theorem 5.1), so if $p$ is a duality property for books with three pages then $p$ holds for general graphs.</p>

CC BY-SA 3.0
2015-05-04T18:19:46.480Z
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.
Hung Le
CC BY-SA 3.0
2015-05-04T18:24:54.400Z
I also updated the question so that it clearer.
Hung Le
CC BY-SA 3.0
2015-05-05T08:24:52.700Z
@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?
Saeed
CC BY-SA 3.0
2015-05-05T15:18:10.997Z
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.
Hung Le
CC BY-SA 3.0
2015-05-04T12:03:42.953Z
2015-05-04T12:03:42.953Z
Saeed
<p>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. <strong>The vertices of the graph are required to lie on this boundary line</strong>, and the edges are required to stay within a single half-plane". Full definition is at (<a href="http://en.wikipedia.org/wiki/Book_embedding" rel="nofollow">http://en.wikipedia.org/wiki/Book_embedding</a>)</p>

<p>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?  </p>

<co.combinatorics><planar-graphs><embeddings>
Book Embedding Duality of Graphs
Hung Le
# Book Embedding Duality of Graphs

(Asked by: username_0 on 2015-05-03)

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?

**Tags:** co.combinatorics, planar-graphs, embeddings

---

## 2 answers

### Answer by username_1 on 2015-05-05. Score: 3

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](http://arxiv.org/abs/cs.DS/0207082)" (SODA'03).


---

### Answer by username_2 on 2015-05-04. Score: 2

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.1728) Theorem 5.1), so if $p$ is a duality property for books with three pages then $p$ holds for general graphs.

> **Comments:**
> **username_0**: 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.  
> **username_0**: I also updated the question so that it clearer.  
> **username_2**: @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?  
> **username_0**: 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.  

---

