1
$\begingroup$

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.

If a graph $G$ is a finite covering graph of graph $B$, is there any relation between their pagenumber?

I think the covering graph is more complicated than the basis graph. So does $pn(G)\geq pn(B)$ hold in general?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The graph of the icosahedron is a 2-fold cover of $K_6$; this covering can be induced by the covering of the projective plane by the sphere. The graph of the icosahedron is planar and Hamiltonian, so its page number is at most $2$, and since it is not outerplanar (as pointed out by Bullet51), its page number is exactly $2$. On the other hand, the graph $K_6$ is nonplanar, so its page number is at least $3$. As pointed out by Bullet51 and Jacob.Z.Lee, the page number of $K_6$ is in fact equal to $3$. This shows that the inequality does not hold in general.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Shouldn't the page number be 2 and 3 respectively? The icosahedron is not outerplanar. $\endgroup$
    – LeechLattice
    Commented Jun 22, 2019 at 3:03
  • 1
    $\begingroup$ Yes. the icosahedron graph is planar and Hamiltonian, so its page number is 2 while $pn(K_6)=3$. it is an excellent counter-example. $\endgroup$
    – Jacob.Z.Lee
    Commented Jun 22, 2019 at 8:27
  • 1
    $\begingroup$ Thank you for the correction! Of course, Hamiltonicity of a planar graph implies page number at most 2. I have edited the answer. $\endgroup$
    – Jan Kyncl
    Commented Jun 23, 2019 at 1:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .