A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded.

Let $G$ is a finite covering graph of a graph $B$. The covering graph is more complicated than the basis graph. Hence at the beginning , I thought that $pn(G)$ should be no less than $pn(B)$ in general. Until Jan Kyncl give a counter-example: The graph of the icosahedron is a 2-fold cover of K6, but $pn(icosahedron)=2$ , $pn(K_6)=3$. Does $pn(G)\geq pn(B)-1 $ hold in general?

  • $\begingroup$ If $G$ could be infinite, then for an arbitrary $B$ we can take $G$ as the universal cover, which is a tree and has page number 1. For finite $G$ some lower bound on its page number may be obtained from the average degree of $B$. $\endgroup$ – Jan Kyncl Jun 28 '19 at 0:33
  • $\begingroup$ @Jan Kyncl . Yes. if $G$ is infinite covering, then it is a tree. so pagenumber is 1. But how to get the lower bound by the average degree of base graph $B$? Could you explain for it? $\endgroup$ – Jacob.Z.Lee Jun 28 '19 at 4:57
  • $\begingroup$ If $B$ is connected and $G$ finite cover of $B$, then the average degree of $G$ is equal to the average degree of $B$. Now the subgraph of $G$ contained in each page of a book embedding is outerplanar, even when adding the Hamiltonian path or cycle joining consecutive vertices of the spine. This gives an upper bound on the average degree of $G$ approximately $2(pn(G)+1)$. $\endgroup$ – Jan Kyncl Jun 29 '19 at 1:46
  • $\begingroup$ @JanKyncl Thanks. Actually, if $G$ is a graph with $V$ vetices, $E$ edges, then $pn(G)\geq [\frac{E-V}{V-3}]>\frac{E-V}{V}$. $\endgroup$ – Jacob.Z.Lee Jun 30 '19 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.