一般闭曲面F2上最优1-嵌入图（O1EG）的任意子式存在性

《Discrete Mathematics》：Minors in optimal 1-embedded graphs

　　

已知任何最优1-平面图（optimal 1-planar graph, O1PG）都含有一个K₆子式（minor），而那些具有K₇子式的图已被完全刻画。此外，其中一名作者证明了对于任意图H，存在一个以H为其拓扑子式（topological minor）的最优1-平面图。本文研究了在一般闭曲面（closed surface）上的最优1-嵌入图（optimal 1-embedded graph, O1EG），并调查了它们所包含的子式。特别地，研究人员证明了对于任意图H，在闭曲面F₂上的每一个最优1-嵌入图，若其四边形子图（quadrangular subgraph）具有足够大的表示性（representativity），则它包含H作为子式。需要注意的是，该研究结果中的H不一定在F₂上是1-可嵌入的（1-embeddable）。

在拓扑图论与图结构理论中，图的子式（minor）关系构成了理解图类结构的核心工具。对于定义在球面上的1-平面图（1-planar graph），其子类最优1-平面图（optimal 1-planar graph, O1PG）的子式理论已相对完善。Mader的经典结果指出，任何具有足够多边的简单图均包含K₆作为子式，由此可推知每个O1PG都含有K₆-minor。进一步地，Suzuki完全刻画了含有K₇-minor的O1PG结构，并证明了对于任意图H，均存在某个O1PG以H为其拓扑子式（topological minor）。然而，当研究背景从球面推广至一般闭曲面（closed surface）F₂时，最优1-嵌入图（optimal 1-embedded graph, O1EG）的子式结构因受曲面拓扑非平凡性的影响而变得极为复杂。具体而言，在不可球面闭曲面上，嵌入的剖分性质与边的交叉模式相互耦合，球面已有的子式结论无法直接平移。因此，探究在何种拓扑条件下，O1EG能够包含任意给定图H作为子式，成为该领域亟待深入的关键问题。

针对上述问题，研究人员在本篇工作中将球面O1PG的经典结果系统推广至一般闭曲面F₂上的O1EG。通过深入分析O1EG的四边形剖分结构，研究人员证明了核心定理（Theorem 3）：对于任意图H，均存在自然数R₁(H)，使得每个位于非球面闭曲面F₂上的O1EG G，只要其四边形子图（quadrangular subgraph）Q(G)的表示性（representativity，亦称面宽face-width）r(Q(G))不小于R₁(H)，则G必定包含H作为子式。这一结论的重要意义在于，目标图H无需在F₂上是1-可嵌入的（1-embeddable）。这意味着，只要O1EG的底层剖分结构在拓扑意义上足够复杂，该图便具备极强的子式通用性，能够“容纳”任意有限图作为其子式。该结果不仅深化了对高表示性嵌入图子式性质的理解，也为闭曲面上1-嵌入图的图子式理论提供了基础性的存在性定理。

为达成上述研究目标，研究人员综合运用了拓扑图论与图子式理论中的多种关键技术。首先，以Robertson和Seymour的图子式定理作为宏观工具，针对任意图H，先通过引理6构造边界长度为4的圆盘O1EG D使其以H为拓扑子式；随后在辅助四边形剖分K及其4-cycle addition扩张图K?_Q(D)中寻找表面子式（surface minor）定位机制。其次，引入并系统运用4-cycle addition与Q4-addition操作，在保持1-嵌入结构的前提下对剖分进行可控调整。证明的核心难点在于引理7，研究人员通过精巧的归纳构造，结合非交叉弦（non-crossing chord）的排除、非交叉2-路径（non-crossing 2-path）的拓扑障碍分析，以及四边形子图Q(G)的二分性，严格证明了在圆盘O1EG中连接边界上四指定顶点的不交路径存在性。最后，在整体证明中，研究人员通过构建由非交叉边组成的立方体障碍（cube obstruction），确保不同面边界上提取的非交叉环互不干扰，从而在整个曲面O1EG的拓扑结构中严格提取出所需的子式关系。

1. Introduction（引言）
研究人员在该部分系统回顾了1-平面图与1-嵌入图的定义体系，明确了在闭曲面F₂上允许每条边至多有一个交叉的嵌入方式。文章重申了球面O1PG在子式理论方面的已知结论，包括Mader关于边数与K₆-minor的关系、Suzuki对K₇-minor的完整刻画，以及任意图H均可作为O1PG拓扑子式的存在性结果。在此基础上，研究人员引出了Robertson-Seymour定理作为理论参照，明确了以表示性作为控制参数来研究曲面嵌入图子式结构的基本思路，从而确立了本文的研究动机与理论框架。

2. Terminology（术语）
研究人员对证明过程中所需的全部专业概念进行了严格定义。包括：闭曲面F₂上的1-嵌入图与最优1-嵌入图（O1EG）的判定标准，其非交叉边构成F₂的四边形剖分（quadrangulation），记为Q(G)；Q(G)中围成面的4-cycle称为Q-facial cycle，其内部含唯一一对交叉边的区域称为kite region（风筝区域）；与顶点v关联的所有kite region之并的边界构成v的link（连接）。此外，研究人员严格界定了本质简单闭曲线（essential simple closed curve）、图的表示性r(G)（即G与所有本质简单闭曲线交点个数的最小值）、k-表示性（k-representative）、局部平面图（locally planar graph）以及表面子式等核心拓扑不变量，并引用了关于O1EG的Q(G)为3-连通且3-表示性的多面体图（polyhedral graph）的既有结论，为后续证明奠定了严密的术语基础。

3. Lemmas for proving the main result（证明主要结果的引理）
该部分是全文的技术核心。研究人员首先证明了引理6：对于任意图H，存在一个边界圈长度为4的圆盘O1EG D，使得H是D的拓扑子式。该引理的证明策略基于Suzuki关于O1PG的定理，通过判断H的细分图是否占据某个kite region中的交叉边，来决定是否实施Q4-addition操作以腾出可移除的交叉边对，从而提取出边界为4-cycle的圆盘子结构。随后，研究人员给出了关键引理7：对于圆盘O1EG G及其边界圈C上按序出现的四个不同顶点v₀,v₁,v₂,v₃，存在端点分别为(v₀,v₂)和(v₁,v₃)的不交路径的充要条件是：边界C上不存在违反特定配置的非交叉弦，且不存在违反特定顺序的非交叉2-路径。该引理通过关于顶点数的归纳法证明，在归纳步骤中利用Q(G)作为二分图的性质，构造从v₀到v₂且内部顶点均为黑点的最短路径，以及从v₁到v₃且内部顶点均为白点的最短路径，并借助link的结构与反证法排除路径交叉的可能，从而确立了两条路径的不交性。

4. Proof of the main result（主要结果的证明）
研究人员基于上述引理完成了主定理的严格证明。整体思路如下：首先任取一个非球面闭曲面F₂上的多面体四边形剖分K，将引理6中得到的圆盘O1EG D的剖分Q(D)嵌入K的某一面中，得到复合剖分K_Q(D)；进而对该面内所有面实施4-cycle addition，获得扩张四边形剖分K?_Q(D)。对于目标O1EG G，假设其Q(G)的表示性r(Q(G))足够大，则由Theorem 1，Q(G)包含K?_Q(D)作为表面子式。根据命题8，Q(G)的顶点集可被分解为对应K?_Q(D)顶点的袋子（bag）。接着，研究人员在G中构造依次穿过对应顶点子集V₀,V₁,V₂,V₃的非交叉环C，以及穿过另一组对应顶点子集U₀,U₁,U₂,U₃的非交叉环C'，并通过连接路径L_i将C与C'链接，形成一个仅由非交叉边构成的立方体障碍。该障碍排除了不同面结构之间的交叉干扰。最后，考虑C所围成的圆盘O1EG G_C，利用立方体障碍排除非交叉弦与非交叉2-路径的可能性后，应用引理7提取出两条所需的不交路径，从而证明D是G的子式，进而H作为G的子式成立。

5. Remarks（评述与讨论）
研究人员在讨论部分指出，该工作关于不可球面闭曲面的结果在形式上也可推广至球面上的O1PG，但此时的前提条件需由较大的表示性替换为四边形子图Q(G)具有足够大的grid minor（网格子式）。为在球面上寻找grid minor，研究人员引入了global connectivity（全局连通度）这一不变量，其定义为使图被删去后每个连通分量至多半数顶点的最小顶点集基数；该概念与tree-width（树宽）密切相关，而tree-width足够大时便保证大grid minor的存在。尽管在曲面嵌入图的研究中以表示性更为常用，但研究人员通过global connectivity也建立了与球面情形的联系。最后，文章提出了猜想9：存在自然数R₂，使得每个位于非球面闭曲面F₂上且满足r(Q(G)) ≥ R₂的O1EG G，都包含K₉作为拓扑子式。该猜想的证明需进一步识别至少九个高度数顶点并确保其不被短非交叉环阻塞。

综上所述，该研究的核心结论可概括为：对于任意图H，在不可球面闭曲面F₂上存在一个仅依赖于H的自然数阈值R₁(H)，使得每个最优1-嵌入图G，只要其四边形子图Q(G)的表示性r(Q(G))达到该阈值，则G必然以H为其子式。值得注意的是，H本身无需在F₂上具有1-可嵌入性。这一发现深刻揭示了拓扑复杂度足够高的最优1-嵌入图具有极端的子式通用性，为闭曲面上1-嵌入图的图子式理论提供了基础性的存在性定理，也为后续研究球面上的对应问题以及K₉拓扑子式的猜想提供了关键的理论工具。