论文标题
支持图形故事的小点集
Small Point-Sets Supporting Graph Stories
论文作者
论文摘要
在图形故事中，顶点一次输入一个图形，每个顶点都以固定的时间$ω$（称为查看窗口）保留在图中。在任何时候，用户只能在查看窗口中看到由顶点引起的图形的图，这确定了一系列图。为了可读性，我们要求序列的所有图纸都是平面。为了保留用户的心理图，我们要求在绘制顶点或边缘时，它一生都具有相同的图纸。我们通过仅将顶点映射到$ω+k $给定点来研究整个序列的问题，其中$ k $尽可能小。我们表明：$（i）$问题不取决于特定的点集，而仅取决于其大小； $（ii）$问题是NP-HARD，当通过$ω+K $参数化时，它是fpt; $（iii）$有一些图形故事的家庭可以用$ k = 0 $绘制任何$ω$，而对于$ k = 0 $，$ω$的小价值却是可以绘制的图形故事的家庭，而其他人则无法绘制； $（iv）$有一些图形故事的家庭无法为任何固定的$ k $绘制，以及至少需要一定$ k $的图形故事。
In a graph story the vertices enter a graph one at a time and each vertex persists in the graph for a fixed amount of time $ω$, called viewing window. At any time, the user can see only the drawing of the graph induced by the vertices in the viewing window and this determines a sequence of drawings. For readability, we require that all the drawings of the sequence are planar. For preserving the user's mental map we require that when a vertex or an edge is drawn, it has the same drawing for its entire life. We study the problem of drawing the entire sequence by mapping the vertices only to $ω+k$ given points, where $k$ is as small as possible. We show that: $(i)$ The problem does not depend on the specific set of points but only on its size; $(ii)$ the problem is NP-hard and is FPT when parameterized by $ω+k$; $(iii)$ there are families of graph stories that can be drawn with $k=0$ for any $ω$, while for $k=0$ and small values of $ω$ there are families of graph stories that can be drawn and others that cannot; $(iv)$ there are families of graph stories that cannot be drawn for any fixed $k$ and families of graph stories that require at least a certain $k$.
