论文标题
图形产品的嵌入
Book Embeddings of Graph Products
论文作者
论文摘要
图形的A $ K $ stack布局（也称为$ K $ page book嵌入）由顶点的总顺序组成，并且将边缘分为$ k $的非交叉订单相对于顶点订单。图的堆栈编号（书籍厚度，页码）是最低$ k $，因此它承认$ k $堆栈的布局。类似地定义了$ k $ - 标题布局，除了可以嵌套单个组中的两个边。 最近证明，各种非限制类别的图形是路径强产物的子图和带有界树宽的图的图。在这种分解结果的动机上，我们探索了图形产品的堆栈布局。我们表明，堆栈数是针对路径的强乘积和（i）有界路径的图形或（ii）有界树宽和边界度的两部分图的图。结果是通过同时堆栈标题布局的新颖概念获得的，该概念可能具有独立的兴趣。
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.
