%0 Generic %1 pupyrev2020embeddings %A Pupyrev, Sergey %D 2020 %K 3330 graph graph_embedding %T Book Embeddings of Graph Products %U http://arxiv.org/abs/2007.15102 %X A $k$-stack layout (also called a $k$-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into $k$ sets of non-crossing edges with respect to the vertex order. The stack number (book thickness, page number) of a graph is the minimum $k$ such that it admits a $k$-stack layout. A $k$-queue layout is defined similarly, except that no two edges in a single set may be nested. It was recently proved that graphs of various non-minor-closed classes are subgraphs of the strong product of a path and a graph with bounded treewidth. Motivated by this decomposition result, we explore stack layouts of graph products. We show that the stack number is bounded for the strong product of a path and (i) a graph of bounded pathwidth or (ii) a bipartite graph of bounded treewidth and bounded degree. The results are obtained via a novel concept of simultaneous stack-queue layouts, which may be of independent interest.

@misc{pupyrev2020embeddings, abstract = {A $k$-stack layout (also called a $k$-page book embedding) of a graph consists of a total order of the vertices, and a partition of the edges into $k$ sets of non-crossing edges with respect to the vertex order. The stack number (book thickness, page number) of a graph is the minimum $k$ such that it admits a $k$-stack layout. A $k$-queue layout is defined similarly, except that no two edges in a single set may be nested. It was recently proved that graphs of various non-minor-closed classes are subgraphs of the strong product of a path and a graph with bounded treewidth. Motivated by this decomposition result, we explore stack layouts of graph products. We show that the stack number is bounded for the strong product of a path and (i) a graph of bounded pathwidth or (ii) a bipartite graph of bounded treewidth and bounded degree. The results are obtained via a novel concept of simultaneous stack-queue layouts, which may be of independent interest.}, added-at = {2020-07-31T08:58:10.000+0200}, author = {Pupyrev, Sergey}, biburl = {https://www.bibsonomy.org/bibtex/2c6af4ca6ab5e63337423d40f3aa43815/j.c.m.janssen}, description = {Book Embeddings of Graph Products}, interhash = {082b71cc7a2af49c03967ae4f1b2aed9}, intrahash = {c6af4ca6ab5e63337423d40f3aa43815}, keywords = {3330 graph graph_embedding}, note = {cite arxiv:2007.15102}, timestamp = {2020-07-31T08:59:14.000+0200}, title = {Book Embeddings of Graph Products}, url = {http://arxiv.org/abs/2007.15102}, year = 2020 }