理论计算机科学电子笔记225（2009）245-253www.elsevier.com/locate/entcs平面图科尔姆奥 Du'nlaing1，2爱尔兰都柏林三一学院数学系摘要本文给出了平面3连通图的一个简单刻画，它具有重心映射和更一般的凸组合映射是嵌入的性质。这在数值分析（网格生成）和计算机图形学（图像变形，表面三角剖分，纹理映射）中有应用：参见[2，11]。关键词：3-连通结点图，平面图。1主要结果本文对预印本[7]中给出的材料进行了略微压缩，其中包含了完整的定义和证明。我们遵循图的通常定义，包括路径，简单路径，循环，简单循环和连通性：[4]是这个主题的有用来源。图的公认定义不允许自环、多重边或无限顶点集，因此它是Tutte语言中的有限简单图§1.1公约：循环继承人和前任。如果一个循环有序列表x1，... ，xn给定，xi+1表示xi的循环顺序的后继，即，x1+（imodn）;类似于xi−1。若当曲线是R2中与圆S1同胚的曲线.命题1.2（约当曲线定理）[5]。 如果C是Jordan曲线，则R2\C有两个路连通分支X，Y，X有界，Y无界，<$X=<$Y = C（<$X是X的边界）。Q1 这些结果已提交给2006年8月在爱尔兰科克举行的第四届爱尔兰MFCSIT会议。2电子邮件地址：odunlain@maths.tcd.ie1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.078246C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）24578654 34 31212Fig. 1.具有不同平面嵌入的图。此外，重心映射不是嵌入。我们遵循图的平面嵌入和平面图的通常定义[4]，平面图意味着允许平面嵌入，但通常我们将考虑特定平面嵌入来谈论平面图。一个非常重要的区别是，平面嵌入图有一个确定的外部面，而在没有规定嵌入的平面图中，没有外部面的概念，甚至可能没有面的概念。图1显示了一个具有两个完全不同嵌入的平面图。引理1.3平面嵌入图G是连通图当且仅当对每个面F，G的子图边界线F是（路）连通的。Q直边嵌入是将边映射到直线段的平面嵌入。命题1.4每个平面图允许一个直边嵌入[1，6，8]。Q命题1.5（欧拉公式）[ 5 ]。如果G是一个平面（直边）嵌入图，则v−e+f=c+1，其中v、e、f和c是G.Q定义1.6给定G=（V，E）且S≠V，G\S=（V\S，{{u，v} ∈E：u，v∈/S}）引理1.7设G是一个直边嵌入平面图，其中所有的面边界都是简单圈，u是G的任意顶点。设x1，. ，x，k是u的以逆序连续的邻居的列表。 对于1 ≤ j ≤ k − 1，设Fj是在反对称意义下出现在边（线段）uxj和uxj+1之间的面。(The面Fj不一定是不同的。）设B是由j<$Fj中的边和顶点构成的子图。然后列表x j中的任何两个顶点都通过B\{u}中的路径连接。见图二、证据 B\{u}也是由j（<$Fj\{u}）中的所有顶点和边组成的子图。因为每个面都是一个简单的循环，所以<$Fj\{u}是连接xj到xj+1的路径。因此，B\{u}包含连接所有这些顶点xj的路径。Q5867C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）245247BX1图二、通过避开u的路径连接的u的邻居。引理1.8一个平面直边嵌入图G是双连通的当且仅当该图由一个单顶点或一条单边组成，或每个面的边界是一个简单圈。证据（略）：如果。一个顶点或边是双连通的，所以我们假设每个面的边界是一个简单的圈。G是连通的（引理1.3）。对于任何顶点x和x的所有邻居xj，存在连接这些邻居的避开x的路径（引理1.7）。因此，所有这些邻居都在Glx的同一个分量中，并且由此得出Glx是连通的。因此G是双连通的.(ii)：如果。假设G是连通的，而不是一个顶点或边，并且存在一个面F，它的边界不是一个简单的圈（图）：F是连通的，但包含一个节点x，它的度（在F中，而不是在G中）不同于2。 如果G包含一个度为0的顶点，那么（因为G是非平凡的）G将是不连通的。如果包含一个度为1的顶点，则G是不连通的或不是双连通的。因此，我们可以假设所有的顶点都有度≥2。设u∈<$F是<$F中度≥3的顶点.设x1，.，x，k是按逆序与u相邻的顶点。对于1≤j≤k，xjuxj+1（xk+1=x1）形成入射到u的面的边界的顺时针部分。由于u在中的度≥3，f F，这些路径中至少有两条与F关联，并且与u关联的不同面少于k个。设GJ=G\{u}.G中与u关联的所有面合并为GJ的一个面，而G的其他面被保留。欧拉公式给出v−e+f= 2，因为G是连通的。相应地，对于GJ，vJ− eJ+ f J= 1 + cJ。现在vJ=v− 1，eJ=e−k。因为在GJ中少于k个面合并成一个面，所以fJ>f+1−k。因此vJ−eJ+fJ>v− 1−e +k+f+1−k = 2，所以CJ>1，GJ是不连通的，G不是双连通的。QX4F3X3uF2x2个F1248C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）245图三. 20个点的Delaunay三角剖分和具有相同边界多边形的相同图的重心嵌入。三角化平面图是平面嵌入图，其中每个有界面与三条边关联给定一个平面嵌入图G，其外部边界是一个简单圈，G的重心映射是指将边界顶点映射到凸多边形的角点上，使得每个内部顶点都映射到其相邻顶点的平均值上.更一般地，如果用“适当加权平均”代替“平均"，则得到凸组合映射。图3显示了具有20个顶点的Delaunay三角剖分，以及同一图的重心嵌入节点3连通平面图（下面的定义1.9）是有趣的，因为每个重心映射（Tutte，[10]）和更一般地每个凸组合映射（Floater，[3]）都是嵌入。当G不是3-连通的时，给出反例是容易的。例如，在图1中，任何重心贴图都必须将内部正方形面映射到线段。该图说明了同一个图的不同平面嵌入，该图不是3-连通的。定义1.9一个图G是3-连通的，如果它是双连通的，并且对于G的每两个真子图H和K，如果G=H<$K并且H<$K只包含两个顶点（没有边），则H或K是简单路。命题1.10每一个三连通图是三连通的;每一个没有2度顶点的三连通图是三连通的。（证据省略。）Q§1.11非连通3-连通图的见证人假设G不是3-连通的。我们说H，K，u，v是见证图，如果G=H<$K，H<$K只包含两个顶点u，v而没有边，H和K都不是路图，并且H和K都不等于G.引理1.12（i）给定见证人H，K，u，v，如果L是G中连接H\K的路到K\H，则L包含三个连续顶点r，s，t，其中{r，s} ∈H，并且{s，t}∈K，r∈H\K，t∈K\H，且s∈H<$K，所以s = u或s = v。(ii)任何避开u和v的路径（分别称为圈），除了可能在其端点（分别称为圈，可能只有一次端点）之外，都完全在H或K中。证据 （i）L中的第一个顶点在H\K中，因此第一条边在H中。 类似地C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）245249最后一个边是K。因此，在路径上存在三个连续的顶点r，s，t，其中{r，s} ∈H，{s，t} ∈K。则s∈H<$K，所以s=u或s=v且s与H和K的边关联。(ii)现在设P是一条避开u和v的路，除了它的端点。这包括一个循环的可能性，被看作是一条开始和结束于同一个顶点w的路径：我们允许w，但不允许循环上的其他顶点，等于u或v。如果路径既不完全在H中，也不完全在K中，则它包含一个三元组r，s，t，其中s=u或s=v，矛盾。Q本节的主要结果是定理1.14，它的证明很长。为了缩短它，我们证明引理1.13设G是一个平面嵌入图，其中所有的面边界都是简单圈。则（i）G是一个有两个面的单圈，或(ii) 对于没有两个面F，FJ是FJ是一个简单的循环，如果有3个面，F1，F2，F3，使得Q1=F2，Q2=F3，Q3=F1都是非空的且连通的，因此是简单的路，它们都连接相同的两个顶点u和v，则正好有三个面，G由三条路连接的两个证据由于所有的面边界都是简单圈，G是双连通的，因此是连通的。(i) 设FJ=FJ是一条约当曲线J。根据命题1.2，F是J的内部，FJ是外部，反之亦然，所以G是一个简单的循环，两张脸(ii) W.l.o.g. F1和F2是有界的。它们的交集Q1是一条简单路，这意味着X=F1F2\interior（Q1）。只 有 F1 和 F2 （ 分 别 为 F3 和 F1 ） 满 足 Q1 （ 分 别 为 Q3 ） 的 相 对 内 部 ， 因 此Q1/=Q3。这些是在<$F1上连接u和v的不同路径，因此<$F1=Q1<$Q3。同样，<$F2=Q1<$Q2，因此<$X=Q2<$Q3=<$F3。F3要么是<$F3（命题1.2）的内部，要么是外部，但是F1<$F2是内部，所以F3是外部，即无界面。因此有三个面，G是三条路径Q1<$Q2<$Q3的并集，其中两个节点是公共的。Q定理1.14平面（直边）嵌入图是平面3-连通的，如果它是双连通的，且任意两个面边界的交是连通的。证据 我们可以假设G是双连通的，因为这是节点3-连通性所必需的。因为G是双连通的，它要么是空的，要么是平凡的，要么是一条边，要么每个面都被一个简单的圈所包围。在前三种情况下，图表显然是3-连通且与一个面双连通，所以我们只需要考虑第四种情况，并且可以假设每个面都被一个简单的圈所包围我们可以假设G是直边嵌入的。因此，每个面的边界都是一个简单的多边形。250C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）24512仅当：设F1和F2是不同的面，且F2不连通。R.T.P.G不是连续3连接的。设u和v是F2的不同分量中的顶点.对于i= 1， 2，有两条路径Pi和Qi连接u和v。这些路径是多边形的。也可以在F1中构造一条路径PJ，不严格地说，将P1稍微移到F1中，并将其端点连接到u和v。 得到的路径在F1中，除了它的端点.类似地，我们可以在F2中构造一条路径Pj，除了它的端点。这些路径一起形成一条（多边形）约当曲线J，它只在u和v处与G相交。通过构造，P1<$P2在J内，Q1<$Q2在J外。设H（分别为K）是G它们位于J的内部或J上（分别位于J的外部或J上）。HK中仅有的顶点是u和v，并且HK不包含边。H包含P1<$P2，因此不是路图，因为否则P1=P2，u和v将在2. 同样，K也不是一个路径图。 因此G不是3-连通的。如果：设G是双连通但不是单3连通的，且H，K，u，v是见证人。G有不止一个面，所以所有的面边界都是简单的圈。权利要求1.子图H\K和K\H是非空的。如果K中的每个顶点也在H中，则K中的顶点在H<$K中，即u和v。 或者K没有边，在这种情况下H=G，或者它有边{u，v}并且是一个路图。两者都不可能。因此，H\K和类似的K\H都是非空的。权利要求2. u和v都不是H和K中的孤立点。否则，假设u在K中是孤立的。设L是连接H\K到K\H的任何路径。 根据引理1.12，连接H\K到K\H的每条路径都包含一个顶点u或v，它们与H和K的边关联。根据假设，u不是;所以每一条这样的路径都包含v。根据权利要求1，至少存在一条这样的路，因此G\v不是连通的，并且G不是双连通的。权利要求3. u和v在H\K和K\H中都有邻居。 假设u的所有邻居都在H中。因为u在K中不是孤立的，所以在K中存在与u关联的边{u，t}。但t是u的近邻，因此t∈H∈K，所以t=v。K中与u关联的唯一边是{u，v}。考虑G中连接H\K到K\H的路径。设t是路径与K \ H相交的第一个顶点，s是路径上t之前的顶点。由于{s，t} ∈Kandds∈/K\H，s∈H<$K：s=uors=v。 然而，如果s=u，then，sincet∈K ，t=v和t∈/K\H 。 Therefors=v. 这意味着 从 H\K到K\H的每一个向量都包含v。同样，根据权利要求1，这样的路存在，所以G不是双连通的。这个矛盾表明，u的所有邻元并不都在H中，也不都在K中，v也是如此。权利要求4.顶点u和v共用一个面。否则，让x1，.，x，k是u的邻居。我们知道（引理1.7）它们都由B\u中的路径连接，其中B是与u关联的有界面的边界的并集。假设v与这些面都不相关，这些路径也会避开v。这意味着u的所有邻居都在H或K中，这与权利要求3相矛盾。权利要求5. 顶点u和v至少有两个公共面 设F1，.C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）2452511是在你周围以逆时针顺序与你相关联的面。至少有一张脸，w.l.o.g. F1，与u和v相关.假设没有其他面孔。有两种情况。 如果u或v，w.l.o.g. u是内部顶点，则所有面关联到u的子图是有界的，并且根据引理1.7，子图i≥2（Fi\u）将是连通的，不包含u和v。 那么这个子图中的所有顶点属于H或K。因为它包含了G中u的所有邻居，所以它将与权利要求3相矛盾。如果u和v都是外顶点，则F是外面，并且都有界面对着你避开。 我们再次考虑子图i≥2（<$Fi\u）。 再次这是一个连通子图，包含G中u的所有邻居，并且再次省略u和v都是，所以它的所有顶点都在H或K中，权利要求3也是矛盾的。因此，u和v至少有两个公共面F和FJ。在权利要求6.如果u和v入射到三个面F1、F2和F3，则这些面中至少两个面的边界具有断开的相交。否则，根据引理1.13，G由三条路连接的两个节点u，v组成如果G=HK其中H<$K={u，v}则H或K是路图：G是3-连通的。这个矛盾表明，其中一对Fj是不连通的，正如所声称的那样。权利要求7. 如果恰好有两个面F和FJ与u和v相关联，则F否则，FJ是连接一个顶点uJ和另一个顶点vJ的路径QJ，并且包含连接u和v的子路径Q。不是所有的uJ，u，v，vJ都需要是不同的，但是假设它们在QJ中以该顺序出现。根据引理1.12，Q中的所有顶点都属于H或K：w.l.o.g.到H.边界圈<$F和<$FJ分别包括连接uJ和vJ的另外两条路径Q1和Q2。设J=Q1<$Q2，一条Jordan曲线.如果uJu则J在v处单独满足HK，或者根本不满足，并且由引理1.12，所有J上的顶点加上QJ\Q中的顶点属于H或属于K。如果J上的所有顶点都属于H，那么J外的所有顶点也属于H，因为对于J外的任何顶点y，可以选择将y连接到J中的顶点的最短路径。u和v都不是这条路径上的内部顶点，所以这条路径上的所有顶点都在H或K中（引理1.12），即，H，因为最后一个顶点在H中。我们已经计算了G中的所有顶点：那些在J之外的，那些在J上的，以及那些在都在H中，所以H=G，不成立。另一方面，如果J上和QJ\Q中的所有顶点都属于K，则J之外的所有顶点都属于K，并且H=Q是一个路图，这是假的。这在使用的情况下证明权利要求7uJ，并且在vi =vJ的情况下通过对称。若u=uJ且v=vJ，则Q=QJ：设Q1和Q2分别是在<$F和<$FJ中连接u到v 根据引理1.12，每个子路径Qi包含在H或K中。同样，我们有一条乔丹曲线J=Q1<$Q2。如果u和v不都是外顶点，w.l.o.g.u是内部顶点，则F和FJ是入射到u的有界面，由于FJ=Q，它们是252C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）245见图4。一个3-连通但非三连通的平面三角剖分图按循环顺序连续。设u1（u2）是Q1（Q2）中唯一入射到u和v的面是F和FJ，所以与v不同的u1和u2以及u1和u2由避开u和v的路径连接（引理1.7）。 因此，根据引理1.12，u1和u2都在H或K中，J上的所有顶点也是如此。对于J之外的所有顶点也是如此，所以H=G或H=Q是一个路图，这是一个矛盾。这留下了u和v是具有恰好两个公共面F和FJ的外部顶点的情况，其边界具有连接的交点。由于u和v是外顶点，其中一个面，比如说，FJ因为G不是3-连通的，所以它不是一个简单的圈，并且Q=FJ是连接u到v的一条简单的路（引理1.13）。设Q1和Q2是连接u和v的另一条路径，F（分别为<$FJ=Q<$Q2是外环，一条约旦曲线，Q1将其内部分成两个区域，F是其中之一。设J=Q1<$Q2。它是围绕另一个区域的乔丹曲线。设ui，i= 1，2，是Qi上的第二个顶点。 同样，有一条路径连接u1和u2，它避开了u和v，J上的所有顶点都在H或K中，J内的所有顶点也是如此。如果它们都在H中，则H=G，如果它们都在K中，则H=Q，这是一条简单的路，这个矛盾完成了权利要求7的证明。权利要求6和7合在一起达到了预期的结果。Q§1.15 Chord-free triangulated graphs. 三角剖分平面嵌入图是指每一个有界面都被三条边包围的平面嵌入图。在三角化双连通图中，外部边界是一个简单圈。只有当一个有界面与一个不连通集中的外边界相交时，它才不能是平面3连通的等价地，它的一条边是连接外边界上两个顶点的弦，另外两条边不都在外边界上[11]。一个完全三角化的图是一个外部边界也有三条边的图，所以它是无弦的，因此是3-连通的。根据命题1.10，每个完全三角化的图都是三连通的，但不是每个三角化的图都是三连通的（图4）。引用[1] H. De Fraysseix，J.Pach和R.Pollack（1990年）。如何在网格上绘制平面图Combinatorica10：1，41[2] Michael S.《浮尸》（2002年）。凸组合映射。在Algorithms for Approximation IV，18-23中，J.Levesley，I. J. Anderson和J.C.梅森（编辑），哈德斯菲尔德大学。[3] Michael S.《浮尸》（2003年）。三角剖分上的一对一分段线性映射。Math.Comp.72，685-696.C. Dúnlaing/Electronic Notes in Theoretical Computer Science 225（2009）245253[4] Goos Kant（1993）.平面图绘制算法。博士乌得勒支大学计算机科学系博士论文[5] E.E. Moise（1977年）。二维和三维的几何拓扑47.第47章我的世界[6] 03The Famous Famous（1994）一种类似的实施方案，您可以使用LEDA实施方案进行分析。报告ALCOM-II-429，也作为报告TCDMATH 98-06发表。[7] ColmO'03The Dog（2006） 一般3-连通的并行分析和并行映射。TCDMATH 06[8] 罗纳德·C Read（1987）. 给定边循环序的平面图的一种新作图法在每个顶点。CongressusNumerantii56，31[9] W.T. Tutte（1960年）。 图的凸表示。 Proc. London Math. Soc.（3）10，304-320.[10] W.T. Tutte（1963年）。如何绘制图表。Proc. London Math. Soc.（3）13，743[11]Geo Werrey White（2004）.用于纹理映射的网格参数化。牛津大学本科计算机科学项目。
