CHORDAL COMPLETIONS OF PLANAR GRAPHS

F. R. K. CHUNG AND DAVID MUMFORD

Abstract. We prove that every planar graph on n vertices is contained in a chordal graph with at most cn log n edges for some absolute constant c and this is best possible to within a constant factor.

1. Introduction

A graph is said to be chordal if every cycle with at least 4 vertices always contains a chord. (A chordal graph is sometimes called a triangulated graph in the literature. For graph-theoretical terminology, the reader is referred to [4].) A chordal completion of a graph G is a chordal graph with the same vertex set as G which contains all edges of G. The problem of interest is to find for a given graph a chordal completion with as few edges as possible. Also, it is desirable to have a chordal completion with small maximum degree. These problems are motivated by applications in computer vision and artificial intelligence (for further discussion see Section 6).

We will prove the following:

Theorem 1. Every planar graph on n vertices has a chordal completion with cn log n edges for some absolute constant c.

We remark that there is an O(nlogn) algorithm for constructing a chordal completion of a planar graph. Also, we note that Theorem 1 is best possible to within a constant factor by considering the n by n grid graph, denoted by L_{n}, which has vertex set

V (L_{n}) = {(i, j) : 0 ≤ i, j ≤ n}

and edges joining:

(i, j) to (i + 1, j), 0 ≤ i < n, 0 ≤ j ≤ n,
(i, j) to (i, j + 1), 0 ≤ i ≤ n, 0 ≤ j < n.

Theorem 2. A chordal completion of the n by n grid L_{n} must contain at least c n^{2} log n edges for some constant c. Furthermore, there is a chordal completion of L_{n} with at most 7.75n^{2} log n edges.

Date:

Throughout this paper, all logarithms are to the base 2. The proof of Theorem 2 is due to Paul Seymour.

Theorem 3. A chordal completion of the n by n grid graph must contain a clique of size cn for some absolute constant c.

Consequently, a chordal completion of the n by n grid graph must contain a vertex of degree at least cn.

This paper is organized as follows: Planar separator theorems are used to prove Theorem 1 in Section 2. Section 3 contains the proofs of Theorem 2. Theorem 3 is proved in Section 4 by using the treewidth of graphs. We extend and generalize Theorem 1 to several families of graphs and random graphs in Section 5. Motivations and applications are discussed in Section 6.

2. Separators and chordal completions

In a graph G, a subset S of vertices is said to be a separator if V (G)−S can be partitioned into two parts A and B satisfying the following conditions:

(i): There is no edge joining a vertex in A and a vertex in B.

(ii): The ratio of |A| and |B| is between \frac{1}{2} and 2.

The separator S is also called a bisector if (ii) is replaced by:

(ii’): |A| = |B|.

Tarjan and Lipton [12] proved the following theorem:

Theorem A A planar graph on n vertices has a bisector of size at most C_{0}\sqrt{n}.

The constant C_{0} in the original bisector theorem was 2\sqrt{2}/(1 − \sqrt{2/3}) ≈ 15.413. It was later [7] improved to 3\sqrt{6} ≈ 7.348. Also, there is a linear algorithm for finding a bisector of size O(\sqrt{n}) in a planar graph.

To prove Theorem 1, we need the following lemma:

Lemma Let G be a graph and suppose its vertices are subdivided into three disjoint parts V (G) = V_{1} ∪ S ∪ V_{2}. Assume:

(i) S is a clique,

(ii) V_{1} and V_{2} are not connected by any edge, (iii) V_{k} ∪ S is chordal for k = 1, 2.

Then G is chordal.

The proof of the lemma is immediate: take a cycle C in G. If C ⊂ (V_{1}∪S), C has a chord; if C ⊂ (V_{2} ∪ S), C has a chord; if neither holds, C contains vertices v_{1} ∈ V_{1}, v_{2} ∈ V_{2}, and because V_{1} and V_{2} are not connected directly, C must cross S twice - hence it has a chord.

Proof of Theorem 1:

We shall use repeatedly the process of taking a graph G and a subset S ⊂ V (G) and adding all edges between vertices in S, making S into a clique. We will denote the enlarged graph by G_{/S}. Using this concept, what we will actually show is the following stronger result:

(*): If G is a planar graph with n vertices and H ⊂ V (G) has m vertices in it, then G_{/H} has a chordal completion Ĝ_{/H} with at most:

f(n, m) = C_{1}n log(n) + C_{2}m\sqrt{n} + C_{3}m^{2}

edges. Here C_{1}, C_{2} and C_{3} are universal constants.

To prove (*), we use the bisector theorem on G, writing V (G) = V_{1} ∪S ∪V_{2}, where |V_{1}| = |V_{2}| and |S| ≤ C_{0}\sqrt{n} and S separates V_{1} from V_{2}. Let G_{k} = V_{k} ∪ S, H_{k} = (H ∩ V_{k}) ∪ S and m_{k} = |H ∩ V_{k}| for k = 1, 2. Now use chordal completions (Ĝ_{k})_{/H_{k}} of (G_{k})_{/H_{k}} satisfying (*) and construct Ĝ_{/H} by:

E(Ĝ_{/H}) = E((Ĝ_{1})_{/H_{1}}) ∪ E((Ĝ_{2})_{/H_{2}}) ∪ ((H ∩ V_{1}) × (H ∩ V_{2})).

This graph is chordal: in fact, the subgraph of Ĝ_{/H} on the vertices:

(V_{1} − H ∩ V_{1}) ∪ (H_{1}) ∪ (H ∩ V_{2})

is chordal by the lemma applied to the three subsets in parentheses. Likewise, the subgraph on

(H ∩ V_{1}) ∪ (H_{2}) ∪ (V_{2} − H_{2} ∩ V_{2})

is chordal. Apply the lemma again for the three-way decomposition

V (G) = (V_{1} − H ∩ V_{1}) ∪ (S ∪ H) ∪ (V_{2} − H ∩ V_{2})

and the full graph Ĝ_{/H} is chordal. Using this completion of G_{/H}, we obtain the bound:

f(n, m) ≤ f(\frac{n}{2} + C_{0}\sqrt{n}, m_{1} + C_{0}\sqrt{n}) + f(\frac{n}{2} + C_{0}\sqrt{n}, m_{2} + C_{0}\sqrt{n}) + m_{1}m_{2}.

For any n, we can always make the theorem hold for graphs G with n ≤ n_{0} by making C_{1} sufficiently large. Assuming this has been done, we can make an induction for n ≥ n_{0}, hence we may assume (*) holds for the two smaller graphs. We assume, in particular, that n_{0} ≥ 864 so that the constant C′_{0} = (1 + (2C_{0}/\sqrt{n_{0}}) ≤ 3/2. Moreover take C_{3} = 0.5. Then substituting and simplifying:

f(n, m) ≤ C_{1}n log(n) + 6\sqrt{6}C_{1}\sqrt{n} log(n) + (\frac{\sqrt{3}C_{2}}{2} + 3\sqrt{6}) \sqrt{n}m + 0.5m^{2} +
(log(.75)C_{1} + 9\sqrt{2}C_{2} + 54) n

In order that the right hand side is bounded by C_{1}n log(n)+C_{2}m\sqrt{n}+0.5m^{2}, we first take C_{2} ≥ 12\sqrt{6} + 18\sqrt{2}, e.g. C_{2} = 55, and we get:

f(n, m) ≤ C_{1}n log(n) + C_{2}\sqrt{n}m + 0.5m^{2} +

((log(.75) + 6\sqrt{6}\frac{log(n_{0})}{\sqrt{n_{0}}}) C_{1} + 9\sqrt{2}C_{2} + 54) n.

If n_{0} is big enough, the coeffecient of C_{1} is negative, hence if C_{1} is large enough, the last term can be dropped and the estimate now follows by induction.

This completes the proof of Theorem 1.

3. The chordal completions of grid graphs

Although the construction of a chordal graph for the grid graph follows from the proof of Theorem 1, we here derive a slightly improved upper bound because grid graphs are useful for various applications ( see Section 6).

We consider the a × b grid graph, denoted by L_{ab}, with vertices:

V (L_{ab}) = {(i, j) : 0 ≤ i ≤ a, 0 ≤ j ≤ b}

and edges joining:

(i, j) to (i + 1, j), 0 ≤ i < a, 0 ≤ j ≤ b,
(i, j) to (i, j + 1), 0 ≤ i ≤ a, 0 ≤ j < b.

The boundary of L_{ab} consists of all vertices (i, j) with i = 0, a or j = 0, b.

Instead of considering the chordal completion of L_{ab}, we examine the chordal completion of the graph L̄_{ab}, which is formed from L_{ab} by making the boundary of L_{ab} into a clique, i.e. by adding all edges joining any two vertices in the boundary of L_{ab}. Clearly, a chordal completion of L̄_{ab} is also a chordal completion of L_{ab}.

We now construct L̂_{ab}, which will later be proved to be a chordal completion of L̄_{ab}, by combining the chordal completions of two subgraphs. f(a, b) will denote the number of edges in L̂_{ab}. We assume without loss of generality that a ≤ b, and begin by dividing L_{ab} along the “b-axis” into two grid graphs with sizes as equal as possible. The graph L̂_{ab} includes all edges which appear in the chordal completions of the two halves of L̄_{ab} plus the edges in L̄_{ab}. It is easy to check that, starting from the edges in chordal completions of the smaller graphs, adding the edges connecting the boundaries of the two pieces and subtracting the edges counted twice in their common boundary, the number of edges of L̂_{ab}, denoted by f(a, b) satisfies

f(a, b) ≤ f(a, ⌊\frac{b}{2}⌋) + f(a, ⌈\frac{b}{2}⌉) + (a + b − 1)^{2} − (b mod 2) − \binom{a + 1}{2}.

To construct the completions of the two pieces, now repeat this construction, but now subdividing the two pieces L_{a,⌊b/2⌋} and L_{a,⌈b/2⌉} along the “a-axis”. With a little calculation, this gives us:

f(a, b) ≤ f(⌊\frac{a}{2}⌋, ⌊\frac{b}{2}⌋) + f(⌊\frac{a}{2}⌋, ⌈\frac{b}{2}⌉) + f(⌈\frac{a}{2}⌉, ⌊\frac{b}{2}⌋) + f(⌈\frac{a}{2}⌉, ⌈\frac{b}{2}⌉)

+3(a − 1)^{2} + 4b(a − 1) + \frac{3}{2}b^{2} − \binom{a + 1}{2} − \binom{⌊\frac{b}{2}⌋ + 1}{2} − \binom{⌈\frac{b}{2}⌉ + 1}{2}

≤ f(⌊\frac{a}{2}⌋, ⌊\frac{b}{2}⌋) + f(⌊\frac{a}{2}⌋, ⌈\frac{b}{2}⌉) + f(⌈\frac{a}{2}⌉, ⌊\frac{b}{2}⌋) + f(⌈\frac{a}{2}⌉, ⌈\frac{b}{2}⌉)

+\frac{5}{2}a^{2} + 4ab + \frac{5}{4}b^{2} − \frac{13}{2}a − \frac{9}{2}b + 3

The construction continues in this way, subdividing alternately along the a and b axes, until a = 1. In this case, the chordal completion is just one clique on 2b + 2 vertices, so

f(1, b) = 2b^{2} + 3b + 1.

It is now easy to prove by induction that

f(a, b) ≤ (\frac{5}{2}a^{2} + 4ab + \frac{5}{4}b^{2}) · (log(a) + 2) .

(handling the four cases a, b even/odd cases carefully.) In particular, for n = a = b, we have

f(n) = f(n, n) ≤ 7.75n^{2}(log(n) + 2).

It remains to prove by induction that L̂_{ab} is chordal. Suppose L̂_{a′b′} is chordal for all a′ < a and b′ < b. By construction, L̂_{ab} is the union of the two such smaller chordal graphs, which we denote Q_{1} and Q_{2}, plus edges making the original boundary B of L_{ab} into a clique. Note that in fact B^{∗} = B ∪ (Q_{1} ∩ Q_{2}) is a clique in L̂_{ab}. Now let C denote a cycle in L̂_{ab}. If the vertices of C are entirely contained in B^{∗}, it has a chord. If not, C contains a vertex in the interior of one of the two subgraphs Q_{1} or Q_{2}: suppose it contains v ∈ Int(Q_{1}). If C is entirely contained in Q_{1}, it again has a chord since Q_{1} is chordal. If not, then it contains some vertex in Q_{2} − Q_{1}. Let w_{1} and w_{2} be the last vertices to the left and right of v on C which are in Q_{1}. These vertices must be on the boundary of Q_{1}, hence form a chord of C in L̂_{ab}. Thus every cycle C has a chord.

To complete the proof of Theorem 2, we consider a chordal completion of L_{n}, which is denoted by L̂_{n}. We want to show L̂_{n} has at least cn^{2} log n edges. In L_{n}, there are n^{2} four cycles each must contain a chord in L̂_{n} and therefore there is a trivial lower bound of n^{2} for the number e(L̂_{n}) of edges in L̂_{n}. An edge in L̂_{n} is said to be k-long if it joins two vertices (i, j) and (i′, j′) where |i − i′| = k or |j − j′| = k. We need the following useful fact:

(*): Suppose a cycle C is the boundary of a k-square (isomorphic to L_{k}) in L_{n}. Then C contains a chord in L̂_{n} which is k-long.

Proof of (*): Consider the graph R consisting of C and its chords. Let C′ denote the minimum cycle in R with the property that C′ contains a vertex from each side of C. If C′ contains only three vertices, it is easy to see that C contains a k-long chord. Suppose C′ contains at least four vertices. Since L̂_{n} is chordal, C′ must contain a chord {x, y}. Suppose the chord {x, y} is not k-long, vertices x and y must belong to adjacent sides of C. We can then form a shorter cycle using the edge {x, y} and parts of C′, from y to x. This contradicts the fact that C′ is minimal. Therefore {x, y} must be k-long and (*) is proved.

Now there are (n − k + 1)^{2} different k-squares in L_{n}. Each k-square contains a chord k-long. On the other hand, each edge which is k-long can be a chord of at most k + 1 k-squares. Therefore in L̂_{n} there are at least \frac{(n−k+1)^{2}}{k+1} edges which are k-long. We then have

e(L̂_{n}) ≥ ∑_{k=1}^{n} \frac{(n − k + 1)^{2}}{k + 1} ≥ n^{2} log n − 2n^{2}

Theorem 2 is proved.

4. The maximum degree in chordal completions

This result is an easy translation of the theorems of Robertson and Seymour on graph minors [16]. Before we proceed to prove Theorem 3, we first state a well-known characterization of chordal graphs (see [5, 8, 18]).

Theorem B For a chordal graph G, there is a tree H so that each vertex of G corresponds to a subtree in H and two vertices are adjacent in G if and only if the corresponding subtrees in H have nontrivial intersection.

The treewidth of a graph G is defined as follows: A family F of subsets of vertices is said to be a tree-covering of G if F satisfies the following conditions:

(i): The union of subsets F in F is the vertex set V (G).

(ii): Members of F are indexed by vertices of some tree T.

(iii): Suppose a vertex v is in both F_{a} and F_{b} where F_{a}, F_{b} ∈ F. Then v

is in every F_{c} if c is in the path of T joining a and b. (iv): If u is adjacent to v in G, then there is a F_{c} in F containing both

u and v.

For each tree-covering F of G, the width of F is just the maximum size of F in F. The tree-width of G is defined to be the minimum width over all tree-coverings of G. The following result can be found in [16].

Theorem C The n by n grid graph has treewidth at least cn.

We are now ready to prove Theorem 3.

Proof of Theorem 3:

Let L̂_{n} denote a chordal completion of the grid graph L_{n}. By Theorem B, there is a tree H so that each vertex v of L̂_{n} corresponds to a subtree T_{v} in H. For each vertex w of H, we define F_{w} to be the set of all v in L̂_{n} so that T_{v} contains w. Two vertices u and v are adjacent in L̂_{n} if and only if F_{u} and F_{v} have nontrivial intersection. It is straightforward to verify that {F_{w} : w ∈ H} satisfies (i) to (iv) and is a tree-covering of L̂_{n}. By Theorem C, one of the F_{w}’s must contain at least cn vertices in L̂_{n}. In addition, any two vertices u and v in F_{w} correspond to trees T_{u} and T_{v} with nontrivial intersection (including w). Therefore, by Theorem B, u and v are adjacent in L̂_{n} and L̂_{n} has a clique of size at least cn. Theorem 3 is proved.

5. Chordal completions for other types of graphs

A family F of graphs is called a closed family if for every G in F, by removing one vertex and its incident edges the remaining graph is also in F. A family F of graphs is said to have a bisector function f if F is closed and every graph G in F with n vertices has a bisector f(n). For example, the family of planar graphs has a bisector function 3\sqrt{6}\sqrt{n}. We can now generalize Theorem 1 as follows.

Theorem 4. Suppose a family F of graphs has a bisector function f(n) = cn^{α} for fixed positive values c and α. Then every graph in F on n vertices has a chordal completion with c_{1}n log n edges if α = 1/2; with c_{2}n^{2α} edges if α > 1/2; and with c_{3}n edges if α < 1/2 where constants c_{1}, c_{2}, c_{3} depend only on c.

Proof: The proof is quite similar to that of Theorem 1 except that the number e(n) of edges satisfies the following recurrence inequality

e(n) ≤ 2e(n/2 + cn^{α}) + c^{2}n^{2α}.

Of special interest is the case for graphs with bounded genus:

Theorem 5. A graph of genus g has a chordal completion with c\sqrt{g}n log n edges.

Proof: This follows from the above theorem and the fact that a graph of genus g has a separator of size c\sqrt{gn}(see[10]).

Theorem 6. A graph with n vertices and with no K_{h}-minor has a choral completion with ch^{3/2}n log n edges.

Theorem 7 is a direct consequence of the fact that a graph with no minor K_{h} has a separator of size h^{3/2}\sqrt{n} (see [1]).

P. Erdös first raised the question how large is a chordal completion of a random graph on n vertices with edge density k/n for some fixed k (or random k-regular graphs). The reader is referred to [4] for models of random graphs or random regular graphs. For example, “A random graph has property P ” means that “a graph on n nodes satisfies property P with probability approaches 1 when n approaches infinity.” In particular, we consider random graphs with edge density k/n (i.e., each unordered pair is an edge with probability k/n).

Theorem 7. A chordal completion of a random graph with edge density k/n for fixed k has cn^{2} edges. In fact it contains a complete subgraph on c′n vertices.

Proof: This follows from the following two facts:

Fact 1. A random graph with edge density k/n for fixed k has a separator at least c_{1}n.

Fact 2. A graph with treewidth k has a separator of size k.

Fact 1 can be easily proved by standard probabilistic methods [2] and Fact 2 can be found in [15]. These two facts imply that a random graph with edge density k/n has treewidth c_{2}n and therefore by Theorems A and B, its chordal completion contains a complete subgraph of c_{2}n^{2}/2 edges.

6. Motivations and applications

Increasingly, artificial intelligence has turned to the theory of Bayesian statistics to provide a solid theoretical foundation and a source of useful algorithms for reasoning about the world in conditions of uncertain and incomplete information. This is true both in familiar high-level applications, such as medical expert systems, and in low-level applications such as speech recognition and computer vision (see [13] for an overview, [11] for medical applications, [14] for speech, [9] for vision). However, all serious applications demand probability spaces with thousands of random variables, and some simplification is required before you can even write down probability distributions in such spaces. The reason this approach is even partially tractable is that one assumes there are many pairs of random variables which are conditionally independent, given various other variables. One extremely useful way to describe this sort of probability space is based on graph theory: one assumes that a graph G is given, whose vertices V (G) correspond to the random variables in the application, and whose edges E(G) denote pairs of variables which directly affect each other. What this means is that if v, w ∈ V (G), S ⊂ V (G), and every path from v to w crosses S, then the corresponding variables X_{v}, X_{w} are conditionally independent given X_{S}. As is well-known, this assumption implies that the probability distribution has the Gibbs form:

Pr(X⃗) = \frac{e^{− ∑_{C} E_{C}(\{X_{w}\}_{w∈C})}}{Z}

where C runs over the cliques of G, E_{C} is a measure of the likelihood of the simultaneous values of the variables in the clique C, and Z is a normalizing constant.

A typical problem in this setting is to find the maximum likelihood estimate of the variables X⃗, i.e. the minimum of the so-called energy

E(X⃗) = ∑_{C} E_{C}({X_{w}}_{w∈C}).

Unfortunately, minimizing such complex functions of huge numbers of variables is not an easy task. One situation in which the minimum can be quickly and accurately computed is that studied in dynamic programming [3]. This is the case where the variables can be ordered in such a way that X_{k} is conditionally independent of all but a few of the previous X_{l}’s, given the values of these few. A Markov chain is the simplest example of this, and this approach, under the name of the Viterbi algorithm, dominates research in speech recognition. However, it has turned out that modifications of the dynamic programming perspective are much more widely applicable [11]. In [11], the authors propose using a chordal completion Ĝ of a given graph G. If the cliques in Ĝ are not too large, one can carry out a variant of dynamic programming for Gibbs fields based on G, and compute essentially all marginal and conditional probabilities of interest.

In computer vision, one seeks to analyze a two-dimensional signal, finding first edges and areas of homogeneous texture, secondly using these to segment the domain of the signal and thirdly identifying particular regions as resulting from the play of light and shadow on known types of objects such as faces. The random variables that arise in this analysis are firstly I_{ij}, the light intensity measured by a receptor at a position (i, j) of the camera’s or eye’s focal plane, secondly “line processes” l_{ij} indicating an edge separating adjacent “pixels” (i, j) and (i, j +1) or (i+1, j), and many higher level variables. What interests us is that the measured variables are parametrized by points of a lattice, and that the structures which one calculates are found by examining local interactions of these variables. In fact, even a high level variable like the presence of a face is linked to local areas of the image, rather than the whole image, because a face will usually be a subset of the image domain and its presence is more or less independent of the scene in the background. What this means is that the cliques of the graph involve local areas in the lattice, and do not require long range interaction of the pixel values I_{ij}. The simplest example of such a graph is the simple n by n grid graph L_{n}. In order to apply a dynamic programming like algorithm to computing the ML estimate, we would like to know is how big are the chordal completions of graphs of this sort: how many edges do they have and what are their degrees?

In previous sections, we answer these problems for grid graphs and planar graphs. Unfortunately for the application to computer vision, the lower bounds on the size of the chordal completions of grids are still too big to make the use of dynamic programming or its variants practical in vision: typical values of n are 100 or more, and probability tables for the values of 100 random variables are quite impractical. However, the construction given above for a chordal completion of L_{n} is strongly reminiscent of the approach to vision problems called “pyramid algorithms” [17], e.g. wavelet expansions [6]. This link is interesting to explore.

References

[1] Noga Alon, Paul Seymour and Robin Thomas, A separator theorem for nonplanar graphs, J. of AMS, 3 (1990) 801-808.

[2] Noga Alon and Joel H. Spencer, The Probabilistic Method, John Wiley & Sons, New York, (1991)

[3] R. Bellman, Dynamic Programming, Princeton Univ. Press (1957).

[4] B. Bollobás, Random Graphs, Academic Press, New York (1987)

[5] P. Buneman, A characterization of rigid circle graphs, Discrete Math. 9 (1974) 202-212 [6] P. Burt and E. Adelson, The Laplacian pyramid as a compact image code, IEEE

Trans. on Comm., 31 (1983), 532-540.

[7] F. R. K. Chung, Improved separators for planar graphs, in Graph Theory, Combinatorics, and Applications, Y. Alavi et al eds., (1991), 265-270.

[8] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory B16 (1974) 47-56

[9] R. Geman, Random Fields and Inverse Problems in Imaging, Springer Lecture Notes in Mathematics.

[10] J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separator theorem for graphs with bounded genus, J. Algorithms 5 (1984) 391-407.

[11] Lauritzen and Spiegelhalter, Local computations with probabilities on graphical structures and their applications to expert systems, J.Royal Soc., Part B, 50 (1988) 157-224.

[12] R. J. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979) 177-189.

[13] J. Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann (1988).

[14] L. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proc. of the IEEE, 77 (1989), 257-285.

[15] N. Robertson and P. D. Seymour, Graph minors II, Algorithmic aspects of tree-width, J. Algorithms 7(1986), 309-322

[16] N. Robertson and P. D. Seymour, Graph minor X. Obstructions to treedecomposition, J. Combinatorial Theory B 52 (1991), 153-190.

[17] A. Rosenfeld ed., Multiresolution Image Processing and Analysis, Springer Verlag, 1984.

[18] J. R. Walter, Representation of rigid cycle graphs, Ph. D. Thesis, Wayne State University 1972

Bell Communications Research, Morristown, New Jersey 07960

Department of Mathematics, Harvard University, Cambridge, Massachussetts 02138