The reconstruction of maximal planar graphs. I. Recognition
The reconstruction of maximal planar graphs. I. Recognition
复制标题
最大平面图的重建。
DOI：
10.1016/0095-8956(81)90063-0
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
J. Lauri
中科院分区：
文献类型：
--
作者：
S. Fiorini;J. Lauri
所考虑的所有图 G=(V (G), E (G)) 都是有限且简单的。 G的顶点数和边数分别用n(G)和m(G)表示； n (G) 是 G 的阶。如果 u EV (G)，我们用 N (v) 表示 z’ 的邻居集合。这是与 u 相邻的那些顶点的集合。 k-顶点是化合价为 k 的顶点；我们也写 p (u)= k。如果 V (C [a, b])=(a= uO, u,,..., ut= b) 且 E (Cla, b 1)=(ciui+,: i= 0.l,..., t-1)，则子图 C [a, 61 被称为从 a 到 b 的链。链C[a,b]也表示为av,c2...L!,-,b。如果 C [a, b] 是链，则我们分别用 C [u, b [, C] u, b] 和 C] u, b [ 表示 C [a, b]-b、C [a, b]-a 和 C [a, b]-a-b。设G是嵌入在平面E中的2连通平面图，并设r是G的电路。然后r将E-r划分为两个开放区域，r的内部，Int(r)，和r的外部，Ext(T)，无界区域。 Int(r)的闭包，记为Int(r)，为Int(T)Ur； Ext (T) 的定义类似。如果r是k-电路（即k个顶点上的电路）使得Int (r) n G= 0或Ext (T) n G= 0，则r称为k-面。如果 G 的所有面都是 3 面，则平面图 G 是最大的；如果 G 的边界上有一个面包含 G 的所有顶点，则平面图 G 是外平面的。如果 G 可以以这样的方式嵌入平面，使得 G 除一个面外的所有面都是 3 面，而例外的面是 k 面，则称 G 具有 k 嵌入（或 k 表示）（k > 4）。一个非平面的图，但其每个真子图都是平面的，称为临界图。我们将重复使用以下众所周知的结果：
All graphs G=(V (G), E (G)) considered are finite and simple. The number of vertices and the number of edges of G are denoted by n (G) and m (G), respectively; n (G) is the order of G. If u EV (G), we denote by N (v) the set of neighbows of z’. that is the set of those vertices to which u is adjacent. A k-verfex is a vertex of valency k; we also write p (u)= k. A subgraph C [a, 61 is said to be a chain from a to b if V (C [a, b])=(a= uO, u,,..., ut= b) and E (Cla, b 1)=(ciui+,: i= 0. l,..., t-1). The chain C [a, b] is also denoted by av, c2... L!,-, b. If C [a, b] is a chain, then we denote C [a, b]-b, C [a, b]-a and C [a, b]-a-b by C [u, b [, C] u, b], and C] u, b [, respectively. Let G be a 2-connected planar graph which is embedded in the plane E and let r be a circuit of G. Then r partitions E-r into two open regions, the interior of r, Int (r), and the exterior of r, Ext (T), the unbounded region. The closure of Int (r), denoted by Int (r), is Int (T) Ur; Ext (T) is similarly defined. If r is a k-circuit (that is, a circuit on k vertices) such that Int (r) n G= 0 or Ext (T) n G= 0, then r is called a k-face. The planar graph G is maximal if all the faces of G are 3-faces, and outerplanar if it has a face containing all the vertices of G on its boundary. G is said to have a k-embedding (or a k-representation)(k> 4) if G can be embedded in the plane in such a way that all the faces of G except one are 3-faces, whereas the exceptional face is a k-face. A graph which is non-planar, but each of whose proper subgraphs is planar is called critical. We shall make repeated use of the following well-known results: