论文标题
在串联平行图的混合线性布局上
On Mixed Linear Layouts of Series-Parallel Graphs
论文作者
论文摘要
图形的混合S堆栈Q-Quesue布局由其顶点的线性顺序和将其边缘的划分分成S堆栈和Q队列，因此同一堆栈十字架中没有两个边缘，在同一队列巢中没有两个边缘。 1992年，希思（Heath）和罗森伯格（Rosenberg）猜想每个平面图都允许使用混合的1件1- Queue布局。最近，PupyRev通过证明不承认1堆栈1 Queue布局的平面部分3树的猜想反驳了这一猜想。在本说明中，我们通过证明猜想甚至在2个树（也称为串联平行图）中也不成立来增强pupyrev的结果。
A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and of a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. Recently, Pupyrev disproved this conjectured by demonstrating a planar partial 3-tree that does not admit a 1-stack 1-queue layout. In this note, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs.
