论文标题
关于故事计划问题的复杂性
On the Complexity of the Storyplan Problem
论文作者
论文摘要
由动态图可视化的激励，我们研究了以\ emph {storyplan}形式表示图形$ g $的问题，即具有以下属性的一系列帧。每个帧都是由其顶点的适当定义子集引起的$ g $子图的平面图。在两个连续的帧之间，出现了一个新的顶点，而其他一些顶点可能消失，即那些至少在一帧中绘制的事件边缘的那些顶点。在故事计划中，每个顶点出现并完全消失了一次。对于以一系列连续帧的序列可见的顶点（边缘），代表它的点（曲线）不会在整个序列中发生变化。 请注意，$ g $的顶点以帧顺序出现的顺序是总顺序。在\ textsc {Storyplan}问题中，我们得到了一个图形，我们想决定是否存在其故事计划存在的总数。我们证明了这个问题是NP完成的，并使用两种参数化算法，一个在顶点封面编号中，一个在反馈边缘设置$ G $中的硬度。另外，我们证明，部分$ 3 $ -TREES总是承认一个故事计划，可以在线性时间内计算。最后，我们表明，在给出了作为输入的一部分的顶点的总顺序，并且我们必须选择如何绘制框架的情况下，问题仍然是NP库。
Motivated by dynamic graph visualization, we study the problem of representing a graph $G$ in the form of a \emph{storyplan}, that is, a sequence of frames with the following properties. Each frame is a planar drawing of the subgraph of $G$ induced by a suitably defined subset of its vertices. Between two consecutive frames, a new vertex appears while some other vertices may disappear, namely those whose incident edges have already been drawn in at least one frame. In a storyplan, each vertex appears and disappears exactly once. For a vertex (edge) visible in a sequence of consecutive frames, the point (curve) representing it does not change throughout the sequence. Note that the order in which the vertices of $G$ appear in the sequence of frames is a total order. In the \textsc{StoryPlan} problem, we are given a graph and we want to decide whether there exists a total order of its vertices for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of $G$. Also, we prove that partial $3$-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete in the case in which the total order of the vertices is given as part of the input and we have to choose how to draw the frames.
