固定顶点覆盖数下的固定顺序书嵌入厚度问题研究

### 固定顶点覆盖数下的固定顺序书嵌入厚度问题研究 #### 1. 背景与问题引入 图的书厚度是一个重要的几何不变量，与图的 $k$ 页书嵌入概念直接相关。对于一个整数 $k \geq 1$，图 $G$ 的 $k$ 页书嵌入是将顶点线性放置在一个脊柱（线段）上，边放置在 $k$ 个页面（共享脊柱的半平面）上，使得每条边嵌入在一个页面中且不产生边交叉。图 $G$ 的书厚度 $bt(G)$ 是使得 $G$ 允许 $k$ 页书嵌入的最小 $k$ 值。 当图 $G=(V, E)$ 中顶点的线性顺序 $\prec$ 预先确定并固定时，书厚度问题被称为固定顺序书厚度问题，记为 $fo - bt(G, \prec)$。该问题等价于确定给定的圆图是否可以用最多 $k$ 种颜色进行适当的顶点着色。一般情况下，固定顺序书厚度问题是 NP 完全问题。 最近，有研究提供了一种基于图的顶点覆盖数 $\tau$ 的参数化算法。本文对该算法进行重新分析，并研究了允许页面有最多 $b$ 个交叉的一般固定顺序书厚度问题。 #### 2. 基本概念 - **顶点覆盖**：图 $G=(V, E)$ 的顶点覆盖 $C$ 是 $V$ 的一个子集，使得 $E$ 中的每条边至少有一个端点在 $C$ 中。顶点覆盖数 $\tau(G)$ 是 $G$ 的最小顶点覆盖的大小。 - **相关集合定义**： - $E_C$：所有两个端点都在 $C$ 中的边的集合。 - $E_i$：对于 $i \in [1, n - \tau]$，$E_i = \{u_jc \in E | j < i, c \in C\}$，即一个端点在 $C$ 外且位于 $u_i$ 左侧的所有边的集合。 - $X$：$X = \{x \in [1, n - \tau] | \exists c \in C : u_x$ 是 $c$ 在 $\prec$ 中的直接后继 $\}$，表示 $U$ 中紧跟在覆盖顶点之后的顶点的索引集合。 - **特殊平面图**： - **$k$ - 受限平面图**：对于整数 $k \geq 0$，图 $G$ 是具有脊柱 $L$ 的 $k$ - 受限平面图，如果满足：所有顶点位于水平直线 $L$ 上且顺序固定；所有边位于 $L$ 上方的半平面；$G$ 最多包含 $k$ 个交叉。 - **$k$ - 交叉平面图**：具有脊柱 $L$ 的 $k$ - 受限平面图 $G$ 是 $k$ - 交叉平面图，如果 $G$ 的每条边都参与产生边交叉。一个 $k$ - 受限平面图可以分解为一个最大的 $0$ - 受限平面图和一个 $k$ - 交叉平面图。 #### 3. 固定顺序书厚度算法运行时间的改进界 - **相关定义**： - **有效部分页面分配**：对于图 $G=(V, E)$ 和最小顶点覆盖 $C$，$S$ 是 $E_C$ 中所有可能的无交叉页面分配的集合，$s \in S$。页面分配 $\alpha : E_i \to [1, k]$ 是有效部分页面分配，如果 $\alpha \cup s$ 以无交叉的方式将边映射到页面。 - **可见性**：在有效部分页面分配 $\alpha : E_i \to [1, k]$ 中，顶点 $c \in C$ 在页面 $p$ 上对 $u_t$（$t \in [1, n - \tau]$）是 $(\alpha, s)$ - 可见的，如果可以在页面 $p$ 上从 $u_t$ 到 $c$ 绘制一条边而不与 $\alpha \cup s$ 映射到页面 $p$ 的任何其他边交叉。 - **可见性矩阵**：对于索引 $a \in [1, n - \tau]$，可见性矩阵 $M_i(a, \alpha, s)$ 是一个 $k \times \tau$ 矩阵，其中 $M_i(a, \alpha, s)$ 的 $(p, r)$ 项为 $1$，如果 $c_r$ 在页面 $p$ 上对 $u_a$ 是 $(\alpha, s)$ - 可见的，否则为 $0$。 - **记录集**：对于顶点 $u_i \in U$，记录集 $R_i(s) = \{(M_i(i, \alpha, s), M_i(x_1, \alpha, s), M_i(x_2, \alpha, s), \ldots, M_i(x_z, \alpha, s)) | \exists$ 有效部分页面分配 $\alpha : E_i \to [1, k]\}$。 - **原算法思路**：原算法按从左到右的顺序动态处理 $U$ 中的顶点。对于每个顶点 $u_i \in U$，计算记录集 $R_i(s)$，其中最多包含 $2^{\tau^3 + \tau^2}$ 条记录。所有有效部分页面分配 $E_i \cup E_C$ 被分为最多 $2^{\tau^3 + \tau^2}$ 组，同一组中的所有分配是“可互换的”，并导致存储在 $R_i(s)$ 中一个记录中的相同可见性矩阵。 - **新方法思路**： - 观察到在每个页面上，从顶点 $c \in C$ 到另一个顶点 $u \in U$ 的不可见性本质上由包围 $c$（或 $u$）的一条边决定。因此，$R_i(s)$ 中每个记录的可见性矩阵可以由 $E_i \cup E_C$ 中的一部分边决定。 - 令 $V' = C \cup \{u_1, u_{x_1}, u_{x_2}, \ldots, u_{x_z}\}$。通过在每个页面上移动一些边，可以得到一个简化的分配 $\alpha' \cup s$，使得相应的可见性矩阵可以由端点都在 $V'$ 中的边决定。注意到 $|V'| \leq 2\tau + 1$，这意味着 $\alpha' \cup s$