论文标题
分层路径和线性布局的两个结果
Two Results on Layered Pathwidth and Linear Layouts
论文作者
论文摘要
分层路径是Bannister等人（2015）研究的新图参数。在本文中，我们提出了两个新的结果，这些结果将分层路径宽与两种类型的线性布局有关。我们的第一个结果表明，对于任何图$ g $，$ g $的堆栈数量最多是$ g $的分层路径。我们的第二个结果表明，任何具有轨道号码的图形$ g $最多都具有层次的路径。第一个结果补充了Dujmović和Frati（2018）将分层的树宽和堆栈编号相关的结果。第二个结果解决了Bannister等人（2015年）提出的空旷问题。
Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Our first result shows that, for any graph $G$, the stack number of $G$ is at most four times the layered pathwidth of $G$. Our second result shows that any graph $G$ with track number at most three has layered pathwidth at most four. The first result complements a result of Dujmović and Frati (2018) relating layered treewidth and stack number. The second result solves an open problem posed by Bannister et al (2015).
