On Linear Layouts of Graphs
On Linear Layouts of Graphs
复制标题
关于图的线性布局
DOI：
--
复制
发表时间：
2004
影响因子：
0.7
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
V. Dujmović;D. Wood
在图顶点的总顺序中，没有共同端点的两条边可以是强调交叉、强调嵌套或强调不连。图的一个顶点堆栈（分别为顶点队列、顶点arch）顶点布局由顶点的总顺序和将边划分为k组成对非交叉（非嵌套、非不相交）边组成。在众多应用的推动下，堆栈布局（也称为强调书嵌入）和队列布局在文献中得到了广泛的研究，而本文是第一次研究拱形布局。我们的主要结果是将k-arch图描述为强调（k+1）可着色图；也就是说，图G的集合S最多有k个顶点，使得G S是（k+1）可着色的。此外，我们调查了关于每种布局类型的以下基本问题，并在队列布局的情况下，提供了一些现有结果的简单证明。在给定顶点的固定顺序的情况下，如何划分边呢？每种布局的最大边数是多少？允许每种布局的图形的最大色数是多少？识别每种类型布局的图形的计算复杂度是多少？par包括所有已知的关于这些主题的参考文献的综合参考书目。票面价值
In a total order of the vertices of a graph, two edges with no endpoint in common can be emphcrossing, emphnested, or emphdisjoint. A emphk-stack (respectively, emphk-queue, emphk-arch) emphlayout of a graph consists of a total order of the vertices, and a partition of the edges into k sets of pairwise non-crossing (non-nested, non-disjoint) edges. Motivated by numerous applications, stack layouts (also called emphbook embeddings) and queue layouts are widely studied in the literature, while this is the first paper to investigate arch layouts.par Our main result is a characterisation of k-arch graphs as the emphalmost (k+1)-colourable graphs; that is, the graphs G with a set S of at most k vertices, such that G S is (k+1)-colourable.par In addition, we survey the following fundamental questions regarding each type of layout, and in the case of queue layouts, provide simple proofs of a number of existing results. How does one partition the edges given a fixed ordering of the vertices? What is the maximum number of edges in each type of layout? What is the maximum chromatic number of a graph admitting each type of layout? What is the computational complexity of recognising the graphs that admit each type of layout?par A comprehensive bibliography of all known references on these topics is included. par