1) planar graph
可平面图
1.
A note on 3-list-coloring of planar graphs
关于可平面图的3-列表染色的一个注记
2.
It not only tests a planar graph but also embeds the planar graph on a single line.
该算法不仅能够测试可平面图、寻找非平面图的最大可平面子图 ,而且能够把一个可平面图嵌入在一条直线上 。
3.
In this paper,we use the discharging method to prove that every planar graph with neither 4-,6-and 8-cycles nor triangles at distance less than 2 is 3-choosable.
本文运用Discharging方法证明了每一个不含4,6,8圈且任意两个三角形的距离至少为2的可平面图是3可选择的。
2) outerplanar graphs
外可平面图
1.
This paper investigated the cycle base structures of 2-connected outerplanar graphs on the torus and proved that there is a one-to-one correspondence between the minimal cycle base and two nonhomotopic noncontractible cycles with the shortest total length when fw(G)≥2 and ew(G) > m, m = max{li | 1≤i≤f}(l1,…,lf denote the length of all the non-Hamilton facial walks of G).
研究环面上2-连通外可平面图G在嵌入Π的面宽fw(G)≥2时的圈基理论;给出在面宽fw(G)≥2和边宽ew(G)>m,m=max{li|1≤i≤f}时外可平面图G的最小圈基的结构,其中f记为Π的除Hamilton圈外的面迹数,l1,…,lf,为Π的对应面迹的长;并证明了G的最小圈基与其不同伦的两条长度之和最短的不可收缩圈之间存在一一对应。
2.
In this paper,we investigate the cycle bases structure of 2-connected outerplanar graphs on the plane and the projective plane in the case of ew(G)≥5.
在ew(G)≥5的条件下,研究在平面和射影平面上2-连通的外可平面图的圈基结构,给出在这两种平面上嵌入的最小圈基。
3.
In this paper, we investigate cycle base structures of 2-connected graphs on the projective plane and determine the minimum cycle base structure of 2-connected outerplanar graphs in the case of ew(G)≥5.
研究了射影平面上2 连通图的圈基结构,并给出了在嵌入的边宽度ew(G)≥5时外可平面图的最小圈基结构,证明了最小圈基与最短不可收缩圈之间的一一对应性。
3) Planar Chordable Graph
平面可弦图
4) Maximal out-planar graph
极大外可平面图
5) maximal outerplanar graph
最大外可平面图
6) developable surface
可展平面
补充资料：可平面图
可平面图
graph, planar
可平面图【脚户，户幽r;r，中n几oeK一‘」 可以正则地嵌人平面的图(见图的嵌入(g丑ph而加“ing)).换句话说，图G称为可平面的(p腼)，如果它可以表示在一个平面上，使得图的顶点对应于平面上不同的点，而且平面上对应于图的边的线不通过对应于顶点的点(端点除外)并互不相交.一些问题，如地图的着色、通讯设计、以及电子学中的一些牵涉到借助于平面印刷子电路来实现电路等问题，都可以化归到可平面图的研究.任何连通可平面图的正则嵌人(有不相交边)都牵涉到把平面剖分成若干区域(面).这样的平面剖分称为平率毕甲(phnartnaP).Euler公式(E枉ler forl妞日a) n一m+r=2，其中n是顶点数，m是边数，且r是地图的面数(包括在外部的一面)，可应用于任何平面地图.因此，图凡(。=5的完全图)与凡，，(每部都有3个顶点的完全二部图，亦见二部图(g卫ph，bipartite))都不是可平面的(图1).含酬冈 ks‘汀3，3 图l在某种意义下，这两种图是最小的不可平面图，根据no盯p用书卫一K切rato钻ki定理(Pon奶哪如一K切旧to枯kit坛泊~):一个图是可平面的，当且仅当它不包含一个同胚于凡或K3.，的子图(见图的同胚(g盈phho-~mo甲比m)). 还有别的可平面性(即一个图是否可平面)的判别准则.特别地，一个图是可平面的，当且仅当它的每个非平凡双连通分支有一个圈基21，…，Z，，与一个附加圈Z。，使得G的任一边恰好属于这m十1个圈中的2个圈的一部分(一个圈基(cyde hasis)是一给定图的所有圈的集合的一个子集，它在图的所有圈的集合中关于模2的加法运算是独立的和完全的，见图(g旧ph)). 任一可平面图可以在一平面上表示，使它的所有边都是直线段.任一3连通图(见图的连通度(graph，conn呱i访ty ofa))可以唯一地嵌人一个球面(在球面同胚的意义下).一个可平面图在平面上的每一个嵌人，因而每一个平面地图，可以与它的几何对偶图(dualg艺ph)构成一一对应关系，这种关系可以建立如下:在地图的每个面内取一点作为对偶图的顶点，如果两面有一公共边e，则将这两面所包含的两点用边e’相连，且e’仅与e相交一次(图2中嵌入的图用实线表示，而它的对偶图用虚线表示). <::，’’’’’’厂 、2 \、一__子，， 图2每个面都由三边围成的平面地图称为平面三角剖分(ph比虹曲 ng山tion).有n个顶点的平面三角剖分的边数是3n一6. 在图论中广泛研究的一个课题是可平面图的着色(见图的，色(g区ph colounng));对于不可平面图，研究了以反映它的不可平面性的程度的各种数值特征，这些数值特征包括亏格、图的厚度和糙度、交叉数等(见图的嵌入(脚phjn七司ding))，【补注】关于可平面图和著名四色猜想(four一田】。ur印叨民t切巴)的一个综述报导由0 .Ore给出【Al].所谓四色猜想是每一个可平面图可用四种颜色顶点着色.最近这个猜想已为K .APpel和w.Haken证明，见四色问题(four一colour pmbl曰n).他们的工作的一个好的摘要见【AZI.
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条