×可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）545-556www.elsevier.com/locate/entcs判定网格是否为平面图的拓扑子图是NP-完全的安德烈·伊梅内斯InstitutodeIngenier'ıaMatem'aticaFacultaddeIngenier'ıaUniversidaddeValpara'<$soValpara'<$so，智利蒂娜·珍妮·施密特汉堡大学数学学院德国汉堡摘要拓扑子图包含（TSC）问题是对给定的两个图G和H，判定H是否是G的拓扑子图。众所周知，当H是输入的一部分时，TSC P问题是NP-完全的，当H固定时，它可以在多项式时间内求解，并且它是固定参数的，可以通过H的阶来处理。由于Robertson和Seymour的网格小定理，网格在图论和算法中具有重要意义，我们研究了平面图中网格TSC问题的计算复杂性。更确切地说，我们研究了以下决策问题：给定一个正整数k和一个平面图G，是k k格G的拓扑子图？我们证明了这个问题是NP-完全的，即使限制到平面图的最大程度6，通过一个新的减少从P LANAR M单调3-SAT PPROBLEM。关键词：拓扑子图，子图同胚，剖分，网格，平面图，NP-完全1介绍给定一个图G，G的一条边uv的细分包括删除它和添加一条新的长度为2的路，其端点为u和v。 对于两个图G和H，我们 称H是G的一个拓扑子图，或G包含H的一个剖分，如果G有一个子图同构于H通过反复剖分得到的一个图1第一作者由CONICYT/FONDECYT/INICIACION 11170931和CONI-CYT/PCI/REDES 180151支持。https://doi.org/10.1016/j.entcs.2019.08.0481571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。546A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545G边缘.这个概念出现在例如经典的表征平面图的库拉托斯基。本文研究了平面图中的GRID拓扑子图包含问题的计算复杂性。一般的问题，称为拓扑子图包含（TSC）PROB-LEM或作为S子图同态问题是，确定两个给定图G和H，H是否是G的拓扑子图。尽最大根据我们的知识，对这个问题的研究始于LaPaugh和Rivest[6]的工作，他们观察到，当H是输入的一部分时，TSC P问题是NP完全的。 实际上，当G是n个顶点的图，H是n个顶点的圈时，则解决TSC问题意味着判定G是否包含汉密尔顿循环 自从汉密尔顿C问题仍然是NP完全的当限制到平面图[4]时，也可以得出TSC P问题是是NP-完全的。这是不同的，当图H是固定。Robertson和Seymour [7]著名的图次定理中的一个算法结果是，当H是固定的时，TSC P问题可以在输入图G的阶的时间多项式中求解。然而，他们的结果中涉及的常数是巨大的，这意味着他们的算法的拓扑子图问题是不实用的。对于某些图H，包括完全二分图K3， 3[1]和具有多达七个辐条的轮[3，8，9]，已知更有效的算法。最近，Grohe等人。[5]表明TSC P问题是固定参数可处理的H阶。他们的算法在时间上与f（nH）·n3成比例地求解TSC问题，其中nG和nH分别表示给定图G和H的顶点数，f（nH）不依赖于nG.本文证明了当G是平面图，H是格时，TSC P问题是NP-完全的。更确切地说，我们研究了G_RID_TSC_P问题，即判定给定图G是否包含k×k网格作为拓扑子图，其中k是输入的一部分。我们展示以下内容。定理1.1平面图中的GRID TSC问题当被限制为最大度为6的平面图时换句话说，定理1.1说，在最大度为6的平面图中找到最大拓扑网格子式是NP-困难的。我们对前一个定理的证明是一个新的约化，在第1.4节中概述，从PLANAR M单调 3-SAT P问题，这是NP-完全的[2]。与拓扑子图相关的概念是子图的概念。一个图H是图G的一个子图，如果通过一系列的边收缩、顶点删除和边删除可以从图G得到一个与H同构的图若G包含H作为拓扑子图，则G也包含H作为子图，且当Δ（H）≤3时反之成立此外，对于每个图H，存在一个有限的图列表H1，...，H 1使得G包含H作为子图当且仅当G包含图H1，. H l作为拓扑子图。A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545547X1X2X3C3C4=（x<$1<$x<$2<$x<$3）C1=（x 1x 2x 3）C2C C CC C CD DD DD DCCC CCCC C1.1文件的结构在1.2和1.3节中，我们介绍基本概念和术语。在1.4节中，我们简述了定理1.1证明的归约的主要思想。 在第2节中，我们描述了减少的小工具。在第3节中，这些小工具被用来构造图Gφ，它依赖于一个3-SAT公式φ的单调直线图。最后，在第4节中，我们提出了减少，即，我们证明了Gφ包含一定大小网格的剖分当且仅当φ是可满足的。由于篇幅所限，本研究中的一些定义和技术细节并未正式确立，而是以一种相当简单的方式提出，直观的方式。1.2平面单调3-SAT问题设U={x1，x2，...，xn}是布尔变量的集合，并且C={C1，.，Cm}是U上的子句集，其中每个子句Ci，i∈[m]是at的析取 大多数3个字面值，即来自U或其否定的变量。 则φ=φ（U，C）= C1<$C2<$. . φCm是U上的一个3-SAT公式，如果存在TRUE和FALSE对U中的变量的赋值使得φ等于TRUE，则称之为满足的。如果一个子句C只包含正的或负的文字，则C分别被称为正的或负的。一个3-SAT公式φ称为单调的，如果φ中的每一个子句都是正的或负的，并且如果下面的二分图G是平面的，则称它是平面的：G的顶点集是{x1，…，x n}{C1，.，C m}和{x，C}是G的一条边，当且若子句C使用x或它的否定x′。设φ=φ（U，C）是单调的平面3-SAT公式。考虑一个由水平轴和垂直轴组成的平面上的正交坐标系。φ的单调直线表示是具有以下性质的平面中的绘图，参见图1a）：C3=（x<$1x<$1）C2=（x2x2x3）条款决定分岔线a）单调的直线表示b）将小工具添加到φ=Ci。网格G图1.一、• U中的变量和C中的子句由平面中的成对不相交的矩形表示，每个矩形的边平行于水平轴或垂直轴。• 水平轴与表示U中变量的每个矩形相交，而与表示C中子句的矩形不相交。此外，每个矩形表示CD548A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545≥˜G_（？）指的是G的一个翅膀，在飞机上，C中的肯定分句被绘制在水平轴的上方，并且表示C中的否定分句的每个矩形被绘制在水平轴的下方。• F或e是一个可变的x∈U， 并且对于每个ch子句C ∈C，如果C包含x或x′，则存在一个连接表示x和C的矩形的垂直线段，并且该垂直线段既不与其他垂直线段相交，也不与其他矩形相交。给定一个3-SAT公式φ的单调直线表示，PLANAR M单调 3-SAT P问题是决定φ是否满足。 这个问题是NP完全问题[2]。考虑平面单调3-SAT公式φ=φ（U，C）. 在本文中，我们不区分φ的变量和子句以及它们在R中的矩形表示。此外，不失一般性，我们假设U中的每个变量出现在至少一个肯定子句和至少一个否定子句中，即， φ使用b个文字x和x<$ ，其中e a chx∈U 。此外，我们假设每个ch子句包含正好三个文字，在R中，每个子句都与正好三条垂直线关联。1.3基本定义和术语在本文中，我们使用符号[n]：={1，2，...，n}，其中n∈ N。对于eachk≥3，k×k网格G_n是具有顶点集{（i，j）：i，j∈[k]}和边的g_n设置. {（i，j），（i×，j×）}：|i−i×|+的|j−j×|=1Σ。顶点（i，j）（i∈[k]和j∈[k]）嵌入坐标中的点（i，j）以第一坐标为横轴，第二坐标为纵轴的坐标系，G的每一条边用线段表示。FORK3，G的正则边的唯一无限面称为G的外面，G的另一面称为G的内面.对于i∈[k]，由{（i，j）：j∈[k]}中的顶点在G中诱导的路径称为G的第i个顶点格路径，对于j∈[k]，由{（i，j）：i∈[k]}中的顶点在G中诱导的路径称为G的第j个水平格路径. 因此，G的边称为垂直边或水平边。1.4还原理念考虑PLANAR M单调 3-SAT P问题的实例φ=φ（U，C），即，如图1a中的图R）。为了证明平面图中的格网TSC问题是NP-困难的（定理1.1），我们构造了一个平面图Gφ，并定义了一个适当的值k，使得k×k格网是Gφ的拓扑子图当且仅当φ是满意的.Gφ的构造从k×k网格Gφ开始。 我们提供了用于子句和变量的小工具gadget到子句gadget。每个变量Gadget由一个决策Gadget和多个分叉Gadget组成决策小工具的目的是编码是否A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545549R×φ的变量被设置为TRUE或FALSE，并且子句gadget的目的是确保子句的三个文字中的至多两个被设置为FALSE。分叉和线小工具通过图Gφ复制和传播信息。使用该图，这些小工具被放置到G的一些内面中，即，由长度为4的圈限定的G的面，见图1。我们证明了，如果G φ包含k k格的一个细分H，那么，大致上，除了一些局部的细分，H是Gφ. 在G φ的构造中，对于一个可变小工具，G φ的一条边被删除. 因此，删除Ch会迫使H的相应网格路径弯曲，因此，沿着将该变量连接到正子句或负子句的一些连线小工具的所有网格路径都必须弯曲。 这里，网格路径的弯曲可以被解释为向子句发送值F alse的变量。 子句gadget被放置在G的内面f上，被设计成最多两个网格路径可以弯曲到面f中。因此，如果连 接 到f中的子句gadget的三个变量被设置为F ALSE，其中一个网格路径不能弯曲到面f中，并且G φ不包含k×k网格2小工具在这一节中，我们考虑k×k网格G的正则边界。我们将删除边、细分边、添加新顶点和添加新边称为修改。LetG e是一个平面图，它是由Gemodiff得到的阳离子。为了构造gadget，我们对G的某些内面进行修改。 这些变形通常会将一个G面的内面分割成几个面，或者只是改变内面的边界。在本文中，对于由G的一个由生成一个gadget的多个分支得到的图G，我们称G的一个内面为G的内面，如果必要的话，则将其更新为boundary。在gadget的图中，新的边比G中的边和由细分产生的边更厚。2.1变量小工具可变Gadget由一个决策Gadget和多个分叉Gadget组成决策gadget是变量gadget中编码TRUE的部分或者FALSE赋值给变量。然后，分叉小工具复制了由决策小工具编码的信息根据需要多次。以下定义在整个小工具的构造中使用设f是G的一个内面，设i，j∈[k]满足f是由循环（（i，j），（i+1，j），（i+1，j +1），（i，j+1））。在f面中添加一个左箭头用路径（（i，j），s1，s2，（i，j+1））替换边{（i，j），（i，j +1）}，其中s1和s2是新顶点，并添加边{（i+1，j），s1}和{（i+1，j+ 1），s2}。类似地，我们定义右箭头、上箭头和下箭头。550A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545−C+−f+f−f0f1S2f2s1f3s3f0f 1f 2F3决策小工具考虑G的一条垂直边e。 byf+和f−分别表示G的两个内面，它们的右边边是e，左边边是e。 为x ∈U添加一个决策小工具意味着在f +中添加一个左箭头，在f中添加一个右箭头，并删除边ex= e，参见图2。a) 决策小工具。b) 正分叉。c) 负分叉。图二、决策和分叉小工具。 在部分b）和c）中，突出显示的子图可视化了f0中的bend如何在连接面f2和f3中被分裂成两个b端。面f+和f−分别称为变量x的正面和负面，f+和f−中的新边分别称为变量x的正边和负边分叉小工具粗略地说，正分叉小工具由两个左箭头组成，其中一个稍微扭曲，见图2。更精确地说，考虑G的两个内面f0和f1，使得f1直接在f 0的左边。 用1来表示G在f0和f1 边 界上 的单 元格。 e2和e3分别位于f 1左侧和右侧的边缘。 以下修改适用于添加在f0和f1中有一个正分叉小工具。在f中添加一个向左箭头。细分e2用两个顶点s1和s2再细分e3一次，比如用顶点s3。不失一般性，假设s2和s3有一个共同的邻居。插入新边{s2，s3}和将s1连接到面f1底部和右侧边的公共顶点的新边。面f1和f0称为分叉面，f0又称为正分叉小工具的右连接这就完成了对正分叉小工具的描述。我们添加更多的符号。 用f2和f3分别表示G的内表面，它们直接位于f1的左边和上面。面f2和f3被称为正分叉小工具的左连接面和上连接面，但它们不属于正分叉小工具。通过将正分叉小工具旋转180度来获得负分叉小工具，参见图2，并且用于负分叉小工具的术语被自然地修改。2.1.1组装变量小工具在下文中，我们考虑P lanar M单调3-SAT的实例φ=φ（U，C）。考虑一个变量x∈ U。我们用deg（x）（resp）表示。deg（x））表示x（resp. （x）在条款中。x的变量gadget由deg+（x）正分叉gadget、deg−（x）负分叉gadget组成A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545551+˜分叉小工具的上下连接面、正分叉小工具的左连接面和负分叉小工具的右连接面参见图3。更准确地说，令（f1，e2，...，e d，f d）是面序列上连接面上连接面决策小工具右负分歧gadget联络脸f+f−左下连接正分叉小工具连接面对面连接面底部图3.第三章。 多变的目标。 在高光照的子图中，边exb终止于位置面f+，这导致所有顶部连接面中的弯曲。其中d：= 2（deg+（x）+ deg−（x）），使得fh+1是fh右边的面，所有h∈ [d−1]。 对于每个h ∈ [deg（x）]，面f2 h−1和f2 h根据正分支小工具进行修改，边e2 deg+（ x） +1被移除，对于每个整数h满足deg+（x）+1 ≤h≤ deg+（x）+ deg −（x），面f2 h−1和f2 h根据负分支小工具进行修改。请注意，面f2 deg+（x）和f2 deg+（x）+1会根据一个决策小工具自动修改，我们将其设置为x的决策小工具。此外，在每个顶部添加向上箭头连接面，并且向下箭头被添加到每个底部连接面，分叉小配件的顶部和底部连接面现在被称为X的可变小配件的顶部和底部连接面。最后，对“第一个”正分叉小工具的左连接面和“最后一个”负分叉小工具的右连接面进行以下修改插入左连接面，比如f0，并添加两条新边，使得v0与f0的右边的两端相关联，并将新顶点vd+1插入右连接面fd+1，并添加两条新边，使得vd+1相关联到fd+1的左边缘的两端。 自然地，这些面现在分别被称为x的可变小工具的左连接面和右连接面2.2条款小工具考虑一个肯定分句C∈ C。C的一个肯定子句小配件由G的一个内部面f（称为子句面）和面fl、fb、fr（分别是直接在f的左边、下面和右边的面）（称为连接面）组成。在图4中，描述了肯定从句小工具否定句小工具是从肯定句小工具中旋转180度得到的。它的子句面和它的连接面：直接在子句面的左边、上面和右边的面，相应地被定义552A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545f2′f3′f4F2F3f1′f1′′f1f0′f0′′f0G1G2flfrG4fbG3图四、 A positi veclausegadget. 定义XC={g1，g2，g3，g4}。2.3电线配件wire gadget的任务是将信息从变量gadget传输到子句gadget。设F=（f0，e1，f1，.，e d，f d）是某个整数d的面序列。 然后，F称之为直的，如果d≤ 1或，e h<$e h+1=<$，对所有h∈ [d− 1]。此外，对于整数h ∈ [d− 1] ，如果F不是直的，但F×：=（f0，e1，...，f h）和F××：=（f h，eh+1，...，D）是直的。设F=（f0，e1，f1，.，e d，f d）是直的或几乎直的面序列。 沿着F添加一个线小工具包括以下修改：在F的每个面上添加一个箭头，使箭头指向F，参见图5。如果F在f h处转弯，则只有箭 头 的 一条 边被添加到f h，如图5所示。图五、 沿着面序列F′=（f0′，e′1，f1′，e′2，f2′，e′3，f3′）、F′′=（f0′ ′，e′1′，f1′ ′）和F=（f0，e1，f1，e2，f2，e3，f3，e4，f4）连接小工具。 面f3′、f1″和f4是子句gadget的面，这会导致这些面中的修改。高亮显示的细分沿F ′′和F弯曲。3Gφ的构造考虑P平面 M单调 3-SAT问题的一个例子φ=φ（U，C），其单调直线表示为R.定义n：= |U|m：= |C|. 设k=8m +2n+5。 用yG表示k×k网格，并考虑G的正则嵌入。在下文中，我们描述了将gadget添加到G以构造Gφ的方式。A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545553、、、2ΣX且令FU：=首先，U中变量的变量小工具是一个接一个地添加--另一个在中间一排K（f1，e2，f2， . ，fk-1）是一个直的面序列，其中f1是G的内面，其边界包含格点（1，jv）和（1，jv+ 1），fk-1是G的内面，其边界包含格点（k，jv）和（k，jv+1）. 令U ={x1，.，xn}，并假设x1，...，x n是变量的顺序，表格出现在绘图R中。 对于x1，...，x n被放置，一个接一个地，沿着FU，使得对于x1的可变gadget的左连接面是fm+3，并且对于xn的可变gadget的右连接面是f7m+2n +2。为了证明这是可能的，让di= 2（deg+（xi）+ deg−（xi）），并注意到，x∈U1dh对R的每一条垂直线计数一次，在R中恰好接触三条垂直线。 因此，d1+. +dn=6m，因此，m+2 + 2 n + d1+... + d n= 7 m +2 n +2。用G1表示从G通过以所述方式添加可变gadget而获得的图在下面的翼中，G1中的G面的更多面被选择用于放置子句和线小工具。 利用机翼R上的直线线，我们可以对每个子句C∈C选择G的不同内面fC，对R上的每个垂直线L选择G中的一个直的或几乎直的面序列FL，使得下面两个性质成立（见图1）.(1) 如果L是R中的一条垂直线，将变量x∈U连接到一个正的（或否定）子句C∈C，则面序列FL=（f0，e1，f1.，fd）满足：面f0是一个顶部（分别为底部）对应于x的可变小配件的连接面，面f1是正上方的面（相应地，下面）f0，面fd是子句面fC。面序列FL是不相交的，可能除了最后一个面，它总是一个子句面，并且对于每个子句C∈ C，恰好有三个面序列的最后一个面为fC。(2) F L=（f0，v e1，f1，.， f d）具有至少m + 2的边界距离;G的内面f的基本距离被定义为短-设v，w-路，使得v在f的边界上，w在G的外表面的边界上。 IfFL是几乎直ht面序列，则FL转atfh，其中h≤d− 2。现在我们最终化Gφ的描述。从图 G1开始，对于每个面序列 FL=（ f0，e1，.，f d−1，e d，f d）其中L是R中的一条垂直线，沿F L添加一个线小工具。注意，对于每个子句C∈ C，fC的正上方、正下方、正左侧和正右侧的面以及fC本身迄今为止都没有被修改接下来，对于每一个积极的（消极的）子句C∈ C，添加一个正（负）子句面为fC子句小工具。由于每个gadget的构造、G1的平面性和性质（1），图Gφ是平面的。并且，在图G φ的每个面f中，至多添加一个常数的顶点和边来构造图G φ。因此，Gφ具有关于k的尺寸多项式，也具有关于φ的尺寸多项式。最后，设F+是R中每条垂直线L的所有面序列FL的集合，将x连接到C中的位置v e子句。 类似地，定义Fx−。˜G.更精确地说，让jv=12554A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545˜˜Xflfrfbflfrfb4减少这里，我们证明了第三节中构造的图Gφ包含一个剖分当且仅当公式φ是满足的。4.1如果φ满足假设φ满足。我们证明了Gφ包含一个子图H，它同构于k×k格网的一个剖分确定一个令人满意的分配T：U →φ的{TRUE，FALSE}。L∈x表示G的唯一边，由于到x的变量gadget的决策部分，并定义EU={ex：x∈ U}。进一步地，对于eache={u，v} ∈E（G∈）\EU，设路Pe表示f的u，v-路在G φ的构造中代替e的G φ。设G s是由Gy替换e∈E（G）\EUbyPe 得到的图. 显然，Gφs是G φ的一个子划分，是G φ + E U的一个子图.本文论证了在保持k × k网格子划分的同时，通过引入一些弯曲，从G_s中去掉每条边e∈E_U是可能的。设H是G φ的子图，由Gφ通过以下条件得到。对于每个变量x∈U，T（x）=F ALSE，边ex由x的正边和G φ中连接它们的边e代替。与其他方法不同的是，在H中，不使用ex，边ex弯曲到x的变量gadget的正表面。然后，通过将正面的左边缘插入其左侧的面，来修复使用边缘e的G的网格路径。我们依次重复修复过程，直到所有修复的网格路径都是G φ的顶点不相交路径，如图3和图5中的子图所示。 最终图H沿着F +中的每个面序列弯曲，其中T（x）= F ALSE。类似地，对于每个变量x∈U，其中T（x）=T RUE，将ex弯曲到x的负面，并修复网格路径，使H沿着Fx −中的每个ch面序列弯曲，其中T（x）=TRUE。a) 边el和eb弯成fl和fb。b) 边el和er弯成fl和fr。图第六章在一个积极的条款小工具的局部网格细分为了证明H的构造是可行的，必须检查在H中，子句面边界上的边可以弯曲到子句面中。考虑一个肯定分句C∈ C;下面的论点很容易调整为否定分句。与2.2节一样，用fl，fb和fr表示子句C的连接面，对于每个h∈ {l，b，r}，设eh是fh边界上的唯一边，其中包含A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545555在子句面fC的边界上没有顶点。由于图6中的示例和对称性，很容易看出局部存在网格细分，其中多达两个边eh（h∈ {l，b，r}）同时弯曲到fh因为T是一个令人满意的赋值，所以有一个变量x被C使用，并且满足T（x）=TRUE。用L表示R中连接x和C的线段。由于边ex弯入H中x的负面，因此H的构造不需要沿FL的任何修改。因此，存在一个h∈ {l，b，r}使得ehd在H中不弯曲成fh，并且H的构造是可行的.4.2如果Gφ包含k×k网格现在，假设Gφ包含k×k网格的细分。我们认为φ是满意的。证明的主要部分是下一个引理。定义Xφ=C∈CXC，其中对于每个C∈ C，XC<$V（Gφ）在图4中定义。引理4.1若G φ包含一个同构于k×k格网的子图H，则（i）G φ的外面的边界恰好是H的外面的边界 ，（ii）V（G φ）\ X φ中的所有顶点都在V（H）中.引理4.1的证明请注意，在构造Gφ时，很少会创建次数至少为4的新顶点关于G这些顶点在子句的面中此外，每个子句面可以在H中最多包含5个度为4的顶点。因此，H的大多数4次交顶点必定在V（G）中。因此，H的外表面必须有个顶点，这些顶点是G的外表面的顶点，而H的外表面的顶点不属于子句面。前面的事实允许我们证明，每个子句面实际上包含至多4个顶点，度为4。我们可以得出结论，H的外表面与Gφ的外表面重合，即，(i)满意了。此外，分离论证意味着（ii）是满足的，这完成了引理的证明。引理4.1用来证明φ是可满足的。假设Gφ包含一个子图H，它同构于k×k格网的一个细分。 为了定义对于φ的真值赋值T：U → {TRUE，FALSE}，考虑变量x∈ U。 在H中，x的边ex，弯曲到x的正或负面。设T（x）=TRUE当且仅当ex弯入x的负面。对于一个矛盾，假设有一个肯定分句C∈C不被赋值T满足;下面的内容很容易调整为否定分句。 设x为任意变量，用L表示R中连接x和C线段。 则T（x）= F ALSE因 此 ，ex弯曲到x的正表面。 然后，H沿着FL弯曲。 在R中，正好有三条线段与子句C接触，因此有三个不同的面序列FL，沿着这些面序列中的每一个，以C和H弯曲的连接面结束。然而，最后一个是不可能的，因此，C必须满足。因此，φ有一个令人满意的赋值。556A. Jiménez，T.J.Schmidt/Electronic Notes in Theoretical Computer Science 346（2019）545引用[1] T.浅野子图同胚问题的一种方法。Theoretical Computer Science，38（1）：249[2] M. de Berg和A.霍斯拉维平面上的最优二元空间划分。在我的T。Thai和Sartaj Sahni，编辑，Computing andCombinatorics ： 16th Annual International Conference ， COCOON 2010 ， Nha Trang ， Vietnam ，2010。第216-225页。Springer Berlin Heidelberg，2010.[3] G.法尔小轮的子图同胚问题。离散数学，71（2）：129[4] M. Garey和D.约翰逊计算机与棘手性：NP完备性理论指南。W. H. 弗里曼公司，美国纽约州纽约市，1979年。[5] M. Grohe，K.Kawarabayashi，D.Marx和P.Wollan. 寻找拓扑子图是固定参数的，第479-488页。2011年。[6] A. LaPaugh和R.里维斯特子图同胚问题。Journal of Computer and System Sciences，20（2）：133[7] N. Robertson和P. Seymour。图未成年人。十三.不相交路径问题。Journal of Combinatorial Theory，Series B，63（1）：65- 110，1995.[8] R. Robinson和G.法尔无6轮剖分图的结构与识别Micromica，55（4）：703[9] R. Robinson和G.法尔没有7轮细分的图。离散数学，327（1）：9- 28，2014年。
我的内容管理
展开
