w 3 -. ,. ‘Iwuva'l‘-L’ “c, f ,. Z ‘1 w v . .. f, .K ‘ <. ..‘ V-n . :-~. ’.,,... ....,.., - \ ,, . ,,...r..‘ - ,. u , . 7 . . . ' v ~ , x _ . v A . ,‘ " A .v , ' ‘ ‘ " ‘, . ‘ . .. -. . ‘ - » . _ " '. . - , ,.I, '7‘ W . ‘ 1‘. . u _, '_ ‘ . '1 ‘ ‘ N ,. , - ." ' ‘ ‘l' v ‘ . . n ~ .- ,""‘ '. , h .. ‘ t , ‘ .v‘ . ., ‘ A ..'. ..‘ -v .-. - ‘ ‘ ' ' ‘ ' U.‘ -' MICHIGAN STAT ll! W“ I”! l I! Wit 4757 mm!“ iii This is to certify that the thesis entitled A go” firm“ FOP Sg/fl/ Decmer/j U971? é¥rZZ/3/7 parttzrmti’hj. presented by C5ddfi§w€flefl CA,(,( has been accepted towards fulfillment of the requirements for Ma SI"; 3Y5 degree in S ci‘e M (12, 3”“ /9. my,“ Major professor Date 3107M. 9/ 0.7 639 MS U is an Affirmative Action/Equal Opportunity Institution _._ ——. LIBRARY ”chum State i University x» J ~——- V‘— PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or'betore date duo. DATE DUE DATE DUE DATE DUE Eire gflw" H "i .‘. ‘ MSU Is An Affirmative Action/Equal Opportunity Institution ennui-damn} ALGORITHMS FOR SIGNAL DECODING USING GRAPH PARTITIONING By .C'huang- Chien Chiu A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Electrical Engineering 1991 ABSTRACT ALGORITHMS FOR SIGNAL DECODING USING GRAPH PARTITIONING By Chuang- Chien Chin This work is concerned with graph partitioning algorithm, which can be used to select 06/1?) nodes for evaluation from an N node decoding graph. The theoretical basis for this work is found in the paper by Venkatesh, Deller and Cozzens [1], and it is the primary purpose of this study to develop algorithms for implementing and testing the methods. The small number of nodes selected by the partition will cover a significant number of paths in the decoding graph, offering a cost-effective method for simultaneously evaluating multiple paths. When a pruning strategy is combined with partitioning, the overall graph search complexity is 0(x/1—V). This represents a significant decrease with respect to conventional left-to-right decoding approaches which are usually 0(N). Theoretical and implementation issues involved in the development of computer algorithms for the partitioning procedure are the principal focus of this work. The algorithms are tested on a large graph (103 nodes, 1,200 edges) using a preliminary version of a “multiple stack” search procedure described in [l]. Copyrighted by CHUANG—CHIEN CHIU 1991 ACKNOWLEDGEMENTS The original idea for using graph partitioning techniques in signal decoding con- tained in this thesis was suggested by Professor John R. Deller, Jr., who is my thesis advisor, and Dr. C.G. Venkatesh in CTA Incorporated. I would like to express my gratitude to both of them for their invaluable guidance and helpful suggestions throughout this research. I am also gratefully indebted to Professor Abdol-Hossein Esfahanian and Professor Majid Nayeri, for their time and effort in discussing and reviewing my thesis. A special word of thanks for my thesis advisor, Professor John R. Deller, J r., for all his patience and encouragement and support over last year we have worked together. It is a very nice and unforgettable experience to be his student. This work is supported in part by a grant from CTA Incorporated in Bedford, Massachusetts. iii Contents 1 Introduction and Background 1.1 The Graph Search Problem in Signal Decoding ............. 1.2 The Outline of the Vertex Partitioning Algorithm ........... Planarity of a Finite Graph 2.1 Preliminaries. .............. . ............... 2.2 A Planarity Testing Algorithm and a Topological Embedding . . . 2.3 Creating a Planar Decoding Graph ................. Development of a Partitioning Algorithm 3.1 Planar Separator Theorems ..................... 3.2 An Algorithm for Planar Graph Partitioning ............ Graph Search with Partitioning In Signal Decoding 4.1 Application of the PST to Graph Search Problem ......... 4.2 A Multiple Stack Algorithm for Search with Partitioning ..... 4.3 Application Example ......................... Conclusions and Future Work The Data File for Creating the Large Graph in Section 4.3 The Nodes of the Large Graph ‘ The Planarity Breaking Arcs in the Large Graph The Trained Models for Testing The Surviving Paths in the Stacks iv 11 11 14 19 24 24 30 39 39 40 44 47 51 57 65 68 70 List of Tables 1 The set of vertices in each face except the vertices which are on the chosen cycle ................................. 37 2 The boundary edges of each face. .................... 37 3 The faces located on both sides of the cycle. .............. 38 4 The set of vertices on each side of the cycle. .............. 38 List of Figures ‘DMNOSO‘thODNt-l HHHHHD—‘Ht—‘H mNGOIiBWNt-‘O The condition implied by the Planar Separator Theorem ........ 3 A partitioning algorithm for implementation ............... 7 A procedure for graph partitioning approaches in signal decoding. . . 10 Examples of planar and nonplanar graphs ............ i . . . . 13 A planar graph with ten faces ....................... 14 Kuratowski subgraphs K3,; and K5 ................... 15 The planarity testing algorithm of Demoucron et al. [9] ........ 18 An example of a decoding graph. .................... 20 An example of creation of a planar decoding graph. .......... 23 The condition implied by case (1) in Theorem 6 ............. 27 The condition implied by case (2a) in Theorem 6. ........... 28 The condition implied by case (2b) in Theorem 6. ........... 29 The algorithm for finding the partitioning cycle ............. 32 The planar graph for the example in Section 3.2 ............. 34 The planar embedding of the graph in Figure 14. ........... 35 The breadth-first spanning tree of the graph in Figure 15 ........ 36 The chosen cycle in the graph in Figure 15 ................ 36 A multiple stack decoding algorithm. . . . .............. 42 vi 1 Introduction and Background 1.1 The Graph Search Problem in Signal Decoding Graph theory has long been recognized as one of the most useful mathematical ways to model many real world problems. For signal decoding problems (e.g., speech recog- nition or image reconstruction), Venkatesh, Deller and Cozzens [1] have presented a graph-theoretic strategy for reducing the computational complexity with respect to conventional decoding approaches [2] [3]. The technique, which is based on the Pla- nar Separator Theorem (PST) of Lipton and Tarjan [4], uses a partitioning approach to locate (Xx/N) nodes for evaluation from an N node decoding graph G. Through the evaluation of this relatively small number of nodes, an optimal path for a given observation string is found. Venkatesh, et al. have worked out the theoretical details underlying this method, but no computer algorithms were developed for selecting these “high payoff” nodes of G. Therefore, the main purpose of this research has been to develop algorithms for partitioning and search of graphs in signal decoding. Before presenting the graph partitioning and search algorithms to solve the signal decoding problem, it is important to sketch the underlying theory and discuss its advantages with respect to conventional left-to-right search. The following fact [5] [6] is fundamental to the methods: Every planar graph with N vertices has a set of vertices C of size 0(x/N) which separates the set of vertices A from the set of vertices B, where A, B, C is a partition of the vertices in the given planar graph and the size of A and B are no more than , 33$. The set C is called an (Xx/N) separator. Since the nodes in C separate the graph into two sets of nodes A and B , making it impossible to pass from one to the other without encountering C, the nodes in C must contain many convergent and divergent paths. This condition is shown in Fig. 1. Thus, the nodes of C can be considered as “bottlenecks” in the graph into which many paths converge. The PST, therefore, guarantees the selection of significant nodes (those nodes in C) which will cover many paths. A pruning process [1] is generally included in a search procedure to minimize the number of overall node evaluations. This procedure introduces the risk of pruning the correct (most likely) path. The increased coverage provided by the partitioning procedure will generally provide an acceptable “pruning safety” . The coverage issue is at the heart of the pruning safety factor disscussed above. On the other band, C is relatively small (Ob/N», and these nodes are selected at distributed locations throughout G, rather than always “from the left” which is conventional [2] [3]. Thus, the use of this set can minimize the number of node evaluations. If the procedure for evaluating nodes is very costly, the partitioning approach will greatly improve the computational cost compared to a conventional left-to-right search. Many computational problems on graphs can be performed more efficiently on planar graphs. We shall focus on the problem of finding an appropriate separator C of size 0(\/N) in a planar decoding graph. The details for extending this method to nonplanar graphs are founded in [1] and developing appropriate algorithms for this more general case will be the subject of future research. After the node selection process is completed, the decoding graph will be searched and pruned according to a likelihood measure. A preliminary version of a multiple stack decoding algorithm developed by Deller and reported in [1] will be presented to carry out this procedure. 2 Figure l: The condition implied by the Planar Separator Theorem. A, B, C form a vertex partition in a planar graph such that no edge joins a vertex in A with a vertex inB. 1.2 The Outline of the Vertex Partitioning Algorithm In 1979 Lipton and Tarjan [4] presented a sequential algorithm which takes 0(N) time for finding a separator of size VSN for planar graphs. The Planar Separator Theorem (PST) of Lipton and Tarjan is as follows: Theorem 1 (Planar Separator Theorem [4]) Let G be any N-vertex planar graph having non-negative vertex costs summing to no more than one. Then the vertices of G can be partitioned into three sets A, B, C, such that no edge joins a vertex in A with a vertex in B, neither A nor 3 has total cost exceeding 3%, and C contains no more than 2\/ 2N vertices. The separator theorem described above is a general form pertaining to planar graphs which have nonnegative costs on the vertices. However, for the purpose of partitioning in signal decoding problems, the desired separator theorem is the special case of equal- cost vertices [4, Cor. 2]. The relevant corollary is as follows: Corollary 1 In any N-vertex planar graph G, a subset of vertices C in G is a sep- arator if remaining vertices can be partitioned into two sets A and B such that there are no edges from A to B, and IA], [B] S 33,1. Then the sets A, B, C form a partition of V, and the separatorC is of size M. [A] denotes the number of vertices in A and V is the set of all vertices. In the following discussion, all vertices are assigned equal cost values which sum to unity. The algorithm for the theorem above (see [4]) requires a breadth-first search (BF 3)1 of the graph as input. Theoretically, given a.BFS of a planar graph, a sim- ple cycle separator can be found. This fact was shown in the proof of Lemma 2 in 1A BFS of a graph with respect to some vertex .9 is a labeling of the vertices such that the label of a vertex v is the shortest distance from s to v. [4]. Even though their separator in general is not a simple cycle, according to the PST we still need to find a simple cycle to complete a satisfactory vertex partition in one special case (we will describe this special case in Chapter 3). Finding a simple cycle separator in a planar graph is an interesting and challenging task. In previous research, Miller [5] presented an algorithm to find a small cycle separator for a 2- connected2 graph. However, decoding graphs generally will not be 2—connected. For actual implementation of the partitioning algorithm, finding an appropriate simple cycle to complete the vertex partitioning is essential. In [4], Lipton and Tarjan suggest a planarity algorithm [7] to construct a planar embedding of the planar graph. Through the planar embedding, a vertex partition can be found which satisfies the Planar Separator Theorem. However, the descrip- tion of the planarity algorithm [7] does not provide suficient information for actual implementation. First, the planarity algorithm does not provide direct information for the determination of each face3 of the planar graph, but the boundary of the faces is used to find a satisfactory simple cycle. Secondly, when a simple cycle has been formed, the total number of vertices on each side (inside and outside) of this cycle must be computed, and the determination that neither the inside nor the outside of this cycle has a total number of vertices exceeding % must be made. However, this task is not described in enough detail in their algorithm for actual implementation. In this work we have solved these problems and recommend an algorithm for actual implementation. The algorithm is shown in Fig. 2. The method of Lipton-Tarjan for finding a planar separator was improved in 1982 by Djidjev [8], who obtained a separator of size \/6_N-. Our algorithm is based 2A 2-connected graph is a connected graph which contains no cut vertices. 3A face m a planar embedding is a connected region bounded by edges and vertices; the boundary of a face is regarded as a closed walk. on the solution of Djidjev with a smaller constant‘ to find a vertex partitioning. We make use of the planarity testing algorithm of Demoucron et a1. [9] to find a planarity embedding of the planar graph. The boundary of each face is easily found by Demoucron’s algorithm, and these faces are recorded for future reference. It should be noted that these faces can actually construct a planar representation of the graph G (see Section 2.2). The general outline of the partitioning algorithm is presented here, and its cor- rectness is described in detail later. Let G(V,E) be a planar graph. G consists of a set of vertices, V = {vi}, a set of edges, E = {ekj} (eh, connects vertex v], to vertex v,). N is the total number of vertices. We implement a BFS to partition the vertices into levels according to their distance from some vertex v. Let L(l) be the total number of vertices on level I. For each a 6 (0,1), let la denote a level such that 2151 L(l) < aN and {3&0 L(l) _>_ (IN. The outline of the algorithm is as follows: Step 1 Classify the vertices of G into levels according to their distance from some vertex v in G. Step 2 Find two levels 11,3 and l2/3. Step 3 If there exists a level I in the interval [l1 /3, 12/3] such that L(l) S V6N, then the nodes in the C set are the vertices on level I. Stop. Otherwise, go to step 4. Step 4 Find a nonnegative integer, say j, such that ls/s'i'j-l X W) < 2—31! bins-5+1 ‘Lipton and Tarjan deduced the constant for the separator C is J8, Djidjev improved the constant tO\/6-. Figure 2: A partitioning algorithm for implementation. '2/s+i Z 13(02 3:?- blue-1° If there exists i 6 [0,3] and L(l1,3 - i) + L(lg/3 + i) S V6N, then the nodes in the C set are the vertices on levels L(l173 - i) and L(12/3 + i). Stop. Otherwise, go to step 5. ' Step 5 Find two levels I’ and 1' such that l' .is the highest level and l" is the lowest level which satisfies the following conditions: {fill/3—j-l 3N — 6, then the graph is nonplanar. Theorem 4 (Jordan Curve Theorem [4]) Let C be any closed curve in a planar graph. The removal of C divides the plane into exactly two connected regions, the inside and the outside of C. 2.2 A Planarity Testing Algorithm and a Topological Em- bedding Kuratowski’s Theorem is the earliest characterization of planar graphs. This theorem proves that no planar graph contains either a complete graph on five vertices or a com- plete bipartite graph on six vertices as shown in Figure 6. Even though Kuratowski’s statement is elegant, his condition is not useful as a. practical test of planarity. In 14 (a) (b) \/ 7:: VM Figure 6: Kuratowski subgraphs (a) K33; (b) K5. this work, to test for planarity, we attempt to construct a planar embedding of the given graph. If such a representation can be completed, then the graph is planar; if not, then the graph is nonplanar. Hopcroft and Tarjan [7] were first to show that planarity testing can be done in linear time (0(N)). In their algorithm, they also show how to draw the graph if it is planar. The algorithm starts by finding a simple cycle and adding to it one simple path at a time. Each new path connects two old vertices via new edges and vertices. However, the Hopcroft-Tarjan planarity testing algorithm does not give a clear description of how to determine each face of a planar graph. At the same time, this algorithm is fairly complex and a complete description would require a much more elaborate exposition. It might be possible to employ this eficient planarity testing algorithm in future work to enhance the entire structure of our partitioning graph search algorithm. However, here we apply the less efficient, but simpler and 15 still polynomial time, planarity testing algorithm, due to Demoucron, Malgrange and Pertuist in 1964 [9]. Demoucron’s algorithm is based on a criterion for determining when a path in a graph can be drawn through a face of a partial planar representation of the graph. The planarity testing algorithm of Demoucron et al. is shown in Fig. 7. Before using this algorithm to determine whether a given graph is planar, some preprocessing considerably simplifies the work. Note the following points: 1. If the graph is not connected, then each component should be subjected to planarity testing. 2. If no cycle is found, then the graph is a tree. Therefore, it is planar. 3. If [E] < 9 or N < 5, then the graph must be planar; if IE] > 3N — 6, then the graph must be nonplanar (see Theorem 3). The following definitions will be required: Let G,(v.-,E.-) be a subgraph of G(V,E), a bridge B of G related to G,- is then: 1. either an edge (u,v)EE where (u,v)¢E,- and u,v€V,-, or 2. a connected component of (G— G,-) plus any edge incident with this component. We denote by V(B,G,-) the vertices of attachment of B to G,-. Let H; be an embedding of G,- in the plane. If B is any bridge of G,-, then B is said to be drawable in a face f of H,- if V(B,G,~) are contained in the boundary of f. We write F(B,H,-) for the sets of faces of H; in which B is drawable. The algorithm to follow is based on a very important criterion : If F(B, Hg) = 0, then we cannot obtain further planar subgraph embedding. Thus the algorithm will terminate for nonplanarity. Given a graph G, the algorithm determines an increasing sequence G1,G2,- -- of planar subgraphs of G, and corresponding planar embeddings H1,H2,' -- when G is 16 planar. Through the algorithm, it is easy to record the faces of each subgraph G,-+1 at each iteration i as shown in Fig. 7. The procedure is as follows : 1. If there exists a bridge B such that F(B, H5) = 0, then the graph G is nonpla- nar. Thus, the planarity testing and planar embedding ceases. 2. If there exists a bridge B such that |F(B,H,~)| = 1, then let {f} = F(B,H,-). From the bridge B, choose a path P.- Q B and set G,-+1 = G,- U P,-. Thus, the faces of G,“ can be obtained by drawing P,- in the face I of G5. 3. Otherwise, choose any face f and any bridge B such that f 6 F(B,H,~). From the bridge B, choose a path P,- Q B and set Gg+1 = G,- U P,‘. The faces of G,“ can also be obtained by drawing P,- in the face f of G,-. Note that if G is planar, then by Euler’s formula, IE] - N + 2 farms will be found. Since these faces have been found following implementation of the process shown in Fig. 7, a. fixed planar embedding of the graph G can be constructed. In Chapter 3, this result will be used to find an appropriate vertex partitioning. 17 Find a cycle G; and a planar embedding H1 Of G1 | i8i+l ForeachbtidgeBof F'md a path P; in B connecting two vertices of attachnient. Set Gi+1= G; U Pi' DrawPiinftoEtHj” , r Yes k Choose any 3 andfif ‘ belong to F(BHa) Figure 7: The planarity testing algorithm of Demoucron et al. [9] 18 2.3 Creating a Planar Decoding Graph A simple language graph, an example of a decoding graph, for experimental testing of the partitioning methods is constructed as follows: Consider a set of sentences, 2 = {23,-}, composed of discrete words from the set, W = {10,-}. A sentence (of length T) is of the form, 2,; = wgl, wig, . . . ,wav, where the comma denotes concatenation. Let’s assume that the word set and the sentence length are finite, so that the set of sentences can be representable as a directed graph (digraph), say G(V, A), in which each vertex is associated with only one word, each edge (or dart in the digraph) represents the transition from word to word in sentences, and each path represents a legal sentence. Formally speaking, a Markov language graph G(V,A) consists of a set of vertices, V = {v.-}, a set of edges, A = {Chi} (akj connects vertex v], to vertex v,-), a special vertex 3 6 V indicating the start vertex of each path, and a set of transition weights, {F(vj | v;)}. P(v,- | v,-) is the probability that w(v,-) is followed by w(v,-) in any sentence, where w(vk) denotes the word associated with vertex vi. Moreover, the elements in'the set of complete paths through G (which means that those paths in G begin at s and terminate at some v1.) will have one-to-one correspondence to the elements in 2. An example of a language graph is shown in Figure 8(a). This graph is created from the following list of sentences, each sentence begins with a dummy point, say “0”, the dummy point is the starting vertex 3 of each path in the graph G (or, equivalently, the first word of each sentence in 2). The sentences are : s It is a language graph example 0 It contains a list of sentences 0 He is not very angry c He wants a piece of paper 19 (8) example sentences 1/3 , . g o ”2 . gt; 0 m m 1.0 m 1.0 “P 1.0 h“ C O O O Q2 Time 81“ 1 2 3 4 5 5 (b) | I I I l l l | | | l l l l Observation ms: 3° 18 not very mm Figure 8: (a)An example of a decoding graph. The transition weights are shown on each edge. (b)The boundaries of the observation string are known. 0 She wants me to help her The goal is to find a planar subgraph of the language graph by extracting out the planarity breaking arcs (arcs which make the language graph G nonplanar). Note that the planar subgraph, say G', will include all the vertices in the original graph G. On the other hand, let G(V,E) be the underlying undirected graph of G(V,A), then the undirected version of G(V,A) is the undirected graph formed by converting each edge of G(V,A) to an undirected edge and removing duplicate edges. Since G(V,E) is planar, G(V,A) will also be planar. The way to discover the planarity breaking 20 arcs in the original graph G is as follows: A data file to store the set of sentences 2 is created (remember that each sentence begins with a dummy point e). The sentences are stored in the data file one by one, and every word in a sentence is stored line by line in the data file according to the concatenation of the words in a sentence. After building up a data; file by using the method described above, the data file is read line by line from the top. Whenever a new line is read one' new vertex may be added to the partial graph which has been built up to this point. At the same time, a new edge to the partial graph is added (recall that each edge represents the transition from word to word in sentences). Since the language graph is constructed in this fashion, a directed graph is obtained. However, the digraph created might not be planar. Therefore, when one line is read to'build a partial graph, the planarity testing algorithm discussed in Section 2.2 is used to determine whether the newly added edge will result in nonplanarity. If so, it is extracted from the partial graph and the next line of the data file is read. Finally, a planar graph is obtained. An example showing the creation of the planar graph using this method is shown in Fig. 9. Note that when the data are read and checked for planarity line by line, there are two situations which will never make the graph nonplanar. One is the reading of the dummy point 0, because it is the first word of each sentence, or equivalently, it is the starting vertex of every path in the graph G'. The other is the case in which the entire content of the present line has not been previously entered. After reading in this line, a new path of vertices and edges is added to the partial graph. However, the new path will not cause nonplanarity. Note also that the planar decoding graph constructed by using this procedure is connected. From the discussion of the situations which will never make the graph nonplanar, it can be concluded that the only situation in which the planarity breaking 21 arcs occur is when at least one word of the current line is already resident in some node. The new edge formed by reading in this line which causes nonplanarity is deleted. However, both ends of the edge are “old” nodes in the partial graph. These nodes are still connected to some other nodes in the partial graph created so far. Thus, after reading all data and the construction of a graph by this method, the final graph is a connected planar graph. 22 AAA E”Ei to". 52 age 8MP 0@ s emaiple 0 g. g a . so. ‘OOOQQMAUJ N»- AAMAA "° O§ Spun 3’. 5:." It is gra h is a gra h 9 0 0 language example example O O It is 0 9 a a C) Figure 9: An example of creation of a planar decoding graph. 23 3 Development of a Partitioning Algorithm In this chapter, the x/N-Planar Separator Theorems are discussed and a vertex parti- tioning algorithm for actual implementation is developed. The results in this chapter are closely related to the efl'ective use of the divide-and-conquer‘s strategy for solving problems on planar graphs. 3.1 Planar Separator Theorems For problems defined on graphs, there are some general conditions under which the divide-and-conquer approach is useful. Let ‘1' be a class of graphs closed under the subgraph relation (i.e., if G1 6 ‘It and G2 is a subgraph of G1, then G; 6 W). In [4], an f (N )separator theorem for ‘1' is a theorem of the following form: Theorem 5 There exist constants a < 1, H > 0 such that if G is any N-vertex graph in \It, the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, [A], [B] _<_ aN, [CI 5 ,Bf(N). In 1979, Lipton and Tarjan [4] proved that a \fN-separator theorem (see Theorem 1 in Subsection 1.2) holds for the class of all planar graphs with constants a = g and fl = 2J2. Djidjev [8] improved the constant 5 = 2J2 to \f6- in 1984. The construc- tive proof of these separator theorems depends on two fundamental lemmas. Since the algorithm presented here for finding an appropriate vertex partition is based on Djidjev’s result, a brief description of Djidjev’s separator theorem and the supporting lemmas is necessary. 8In [4], the following three conditions are shown to be necessary for the success and efficiency of divide-and-conquer: (i) the subproblems must be of the same type as the original and independent of each other (in a suitable sense); (ii) the cost of combining the subproblem solutions into a solution to the original problem must be small; and (iii) the subproblems must be substantially smaller than the original problem. 24 Lemma 1 Let G be any N-vertex connected planar graph. Suppose G has a spanning tree of radius r. Then the vertices of G can be partitioned into three sets A, B, C, such that no edge joins a vertex in A with a vertex in B, neither A nor 8 has total number of vertices exceeding 37", and C contains no more than 2r + 1 vertices, one the root of the tree. The proof of the lemma proceeds by first embedding G in the plane and finding a breadth-first spanning tree of G. Since each face is triangulated by adding some additional edges, any nontree edge (including the new added edges) forms a simple cycle with some of the tree edges. Therefore, the length of this cycle is at most 2r +1 if it contains the root of the tree. By the Jordan Curve Theorem (Theorem 4), the cycle divides the graph into two parts, the inside and the outside of the cycle. Lipton and Tarjan [4, Lemma 2] showed by examples that at least one such cycle separates the graph so that neither the inside nor the outside of the cycle contains more than g vertices. Note that the simplest class of graphs with small separators is trees. A tree has the separator C of size 1, and the root of the tree is a proper separator. Lemma 2 Let G be any N-vertex connected planar graph. Suppose the vertices of G are partitioned into levels according to their distance from some vertex 3 and that L(l) denotes the total number of vertices on level I. Given any two levels I' and I" such that the number of vertices on levels 0 through l' - 1 does not exceed 335- and the 2.2! 3 , it is possible to find number of vertices on levels I' + 1 and above does not exceed a partition A, B, C of the vertices of G such that no edge joins a vertex in A with a vertex in B, [A], [B] 5 13,1, [C] S L(l’) + L(l') + max{0,2(l’ - I" -1)}. The lemma is very important for constructing a vertex partitioning algorithm for actual implementation. The proof of the lemma concerns the relationship between levels l' and l'. (i) Suppose I' Z I". Then the lemma is obviously true if we choose 25 all the vertices on level I' to be in the C set, and let A be all the vertices below the level I' and B be all the vertices above the level l'. (ii) Suppose that l' < I". Since the vertices in levels l' and l' are deleted, the graph naturally partitions into three parts: vertices on levels 0 through l' - 1, vertices on I' + 1 through I” - 1, and vertices on levels I" + 1 and above. To find an appropriate vertex partitioning in this condition, two cases must be considered. One is the case in which the total number of vertices between I' + 1 and l' - 1 does not exceed 359,-. A proper partition is obtained by setting A the part of the three with the most vertices, B the remaining two parts, and C the set of vertices in levels l' and l' . The other case is that in which the total number of vertices between I' + 1 and l' - 1 exceeds “-391. In this case, the part between l' + 1 and l' - 1 requires sub-partitioning. A sub-partitioning is carried out as follows: All vertices on levels 1' and above are deleted and all vertices on levels 0 through l' - 1 shrunk to a single vertex x. A new graph“, say G', is formed. Note that the new graph preserves planarity [4, Col 1]. Apply Lemma 1 to the new graph. Let A', B', C' be its vertex partition, the set C' being the vertices on the cycle. Therefore, a proper vertex partitioning of the graph G derives from letting A be the set among A' and 8' with more vertices, C the vertices in levels 1' and 1' plus the set C', and B the remaining vertices. Theorem 6 (Djidjev’s Planar Separator Theorem [8]) Let G be any N-vertex planar graph. The vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, [A], [B] S 33d, [C] S V6N. Since our interest is in partitioning the connected decoding graphs for selecting “high payoff” nodes to evaluate, we simply consider the case of connected graphs in this theorem. The partitioning construction involves classifying the vertices of G into ”Note that the single vertex 2 will not be counted in the total number of vertices in G'. 26 Figure 10: The condition implied by case (1) in Theorem 6. Since we can find the level I satisfying 1 e [11 ,3, l3/3] and L(l) S V6N, an appropriate vertex partition is found. levels according to their distance from some vertex v. Let L(l) be the total number of vertices on level I. Find two levels first, say 11/3 and 12/3, satisfying certain numerical restrictions: For each a 6 (0,1), let I, denote a level such that 23151 L(l) < 0N and Z]; L(l) 2 (IN. (1) If there exists one level between 11/3 and 12/3, say I, such that L(l) S y/6—N, then the set of vertices on levels 0 through I - 1 and the set of vertices on levels I + 1 through above will not exceed %. Let C be the set of vertices on level I. Then the theorem is true. This case is shown in Fig. 10. (2) Otherwise, finding a nonnegative integer, say j, satisfying £3,331!“ L(l) < 2/ 3 . N 27 [2’3 12 TH 00000 0000000000000000 00000000000 000000 A ‘J Figure 11: The condition implied by case (2a) in Theorem 6. and 2:23;, L(l) 2 ¥-. Two subcases must be considered: (2a) If If there exists i E [0,j] and L(11/3 - i) +IL(12/3 + i) S m, then the nodes in the C set are the vertices on levels L(l1/3 - i) and Lag/3 + i). Following the numerical rule for finding j, let A be the set of vertices on levels L(l1/3 - i + 1) through L(lg/a + i — 1) which does not exceed 333, and B the set of the remaining vertices. Thus, this is a proper partition. The case is shown in Fig. 11. (2b) Otherwise, two levels, say l' and l" satisfying the following numerical restrictions, are located. I’_<_I,,3-j-1 I‘Lsu-ths vision dfwhmub [a- m1 UP. j [in/dun ] We ' LII-Inland“ ”i. In Imlmdcdvufis- Figure 13: The algorithm for finding the partitioning cycle in the new graph G'. 32 F.- = F; U {10"} and F. = F, U {”1}. Stop and scan another edge in the chosen cycle. 1 3. Otherwise, put f’ to the inside of the cycle and f” to the outside of the cycle. Set E = E U {VI'} and F, = Fa U {Vf"}' 4. Scan another edge in the chosen cycle. In general, there will be faces which are not incident to any edge in the chosen cycle. If so, the rule described above is used to locate every “unused” face to either the inside or the outside of the cycle. Finally, the vertices on the inside of the cycle and the vertices on the outside of the cycle can be determined. An example will illustrate the method for finding an appropriate cycle separator. The original graph is shown in Fig. 14. By using Demoucron’s planarity algorithm, the boundary of each face is found, and the graph is embedded in the plane. The planar embedding is shown in Fig. 15. The breadth-first spanning tree is shown in Fig. 16. Then one nontree edge, say (3,10), and its corresponding cycle are found. The cycle is shown in Fig. 17. After these processes are completed, three types of data must be recorded. One is the set of edges which forms the cycle. In this example, the edges of the cycle are 1, 17, 15, 14, 12, 7, 4. Another is the set of vertices in each face except the vertices which are on the chosen cycle. This is shown in Table 1. The other is the set of boundary edges for each face. These are shown in Table 2. Now, the rule for determining which faces should be located inside of the cycle and which should be located outside of the cycle is applied. The result is shown in Table 3. From these results, the appropriateness of the chosen cycle as a separator can be determined. This consideration is shown in Table 4. Finally, we note that the vertex partitioning algorithm presented in this chapter can obtain different partitions of the same graph by choosing a variety of reference 33 17 | 16 2 3 9 (3 9 10 1 5 , 4 11 0 0 o a. 15?) 7 1 12 9 CD 9 13 N:- 2; |B|=I=l7 Figure 14: The planar graph. Note that every vertex and edge is labeled. nodes for drawing the level lines. The main criterion in choosing an adequate par- tition is suficient path coverage. In the present stage of the research, choosing an adequate partition of the decoding graph G must be done ofi-line prior to beginning the decoding. 34 Figure 15: Embed the graph in the plane and find the boundary of each face (Using Demoucron’s planarity algorithm). 35 Figure 16: The breadth-first spanning tree of the graph. The bold lines mean tree edges. The node “0” is the root of the tree. Figure 17: Choose one nontree edge from the planar graph, say (3,10), find its cor- responding cycle with some other tree edges. Dotted lines are used to indicate the cycle. 36 face 1 9, 7, 8 face 2 1 face 3 none face 4 5 face 5 5, 1 face 6 9, 8 face 7 9, 7, 8 Table 1: The set of vertices in each face except the vertices which are on the chosen cycle. face 1 16, 11, 9, 2,1 face 2 10, 6,17 face 3 1213.14.15 face 4 4, 5, 7, 8 faceS 1, 6, 10, 15, 14, 12, 8, 5 faccé 16, 3, 2, 17, 13, 7, 4 face 7 11, 3, 9 Table 2: The boundary edges of each face. 37 Result: outside the face 5 face 5 face 5 face 4 Faces have been used to locate in either side of the cycle: face 1, 2, 3, 4, 5, 6. Faces haven’t been used: face 7. Faces inside the cycle: face 1, 3, 6, 7. Faces outsrde the cycle: face 2, 4, 5. Table 3: Two faces to which each edge of the cycle is incident. The faces are located to either side of the cycle. The unused faces are recorded. - Total Vernces number Inside 9, 7’ 3 3( < 2/3N) Outside 1. 5 2 (< 2/3 N) Table 4: The set of vertices on each side of the cycle. 38 4 Graph Search with Partitioning In Signal De- coding 4.1 Application of the PST to Graph Search Problem In this section we give a simple example to illustrate the use of the partitioning methods in signal decoding. Since the primary focus of this work has been on the development of partitioning algorithms, this example is not meant to be completely illustrative of the power of the methods, nor does it dwell upon many important details (to be noted) which will be the subjects of future research. Let’s consider the meaning of G in the decoding problem. Each node in G repre- sents a physical entity in the sense that “resident” at v; is some abstract information or model which represents the entity. For example, the node might represent a word in a language graph (see Section 2.3), and resident at the node would be a statistical model of the word features to be evaluated against measured acoustical observations. Because we are working with a simple speech recognition problem in this example, we will refer to the physical entity which is represented by a node as a word. A legal concatenation of words (path through G) will be called, naturally, a sentence. The evaluation of a node u,- will refer to some quantitative assessment (either likelihood or probability) of the model at v,- with respect to the observations. The decoding prob— lem is to find the most likely path (most likely sentence) in G, given the observation string, say Y, and the a priori structure embedded in G. After using the graph partitioning method to locate 0(\/—1\7) “high payoff” nodes in an N node decoding graph G, the technique for implementing the search of paths must be considered. In conventional “left-to—right” strategies, the evaluation of nodes takes place as they encountered along paths. However, the evaluation of nodes occurs 39 as the selected nodes are encountered along paths in the partitioned case. Since we only evaluate the preselected nodes of the paths in the partitioned case, the search procedures must be modified to accommodate unevaluated nodes. The details of this issue are the subject of the next section. 4.2 A Multiple Stack Algorithm for Search with Partition- ing A conventional left-to-right search can be carried out using a “stack” algorithm [2]. Each evolving path is entered into a “stack” (memory array), its position in the stack determined by its likelihood. The most likely partial path is put at the top of the stack. Since the stack is of finite length, say q, only the q most likely partial paths survive. The finite stack, therefore, effects one type of pruning operation called hard pruning [1]. A second type of pruning occurs when a partial path, for which there is sufficient room in the stack, is deemed too unlikely to be viable and is removed. ' This type of pruning is called sofl pruning. At eaCh iteration, the partial path in the top location of the stack is extended by one word (then paths are rearranged if necessary). When a complete path appears as an entry at the top of the stack, the decoding is complete. To search the paths in the partitioned case, a modified left-to-right procedure is suggested by Deller in [1]. For simplicity, we consider a special case of this procedure in which the temporal boundaries in the observation string, Y, are known. By this we mean that discrete groups of observations are known to be associated with particular time slots in the utterance and can therefore be associated with exactly one word (node in G). Of course which node is unknown, but the known boundaries in Y greatly simplify the search process. The algorithm shown in Fig. 18 pertains to the 40 graph search in which the boundaries of the observation string, Y, are known. Let’s begin generating paths from the leftmost (start) node in G. The evaluation of nodes occurs as the selected nodes are encountered along paths. To provide “fair competition” among partial paths with different numbers of evalua- tions, a separate stack, say 5;, is built for each number of evaluations. 5',- denotes the stack containing partial paths with exactly i evaluated nodes. As the decoding pro- cess procedes, path segments will move into the increasingly “more evaluated” stacks as more selected nodes are encountered. Hard pruning and soft pruning can also be applied to the multiple stack graph search. The harding pruning takes place in each stack when there is room for only, say q,-, partial paths in stack 5;. q,- is assigned for each stack prior to search. Soft pruning occurs in stack .5'; when a partial path with i evaluations falls below some predetermined likelihood threshold, even though there is suficient room for it in 5;. Let ng, denote the substring of observations t1 through t2. Here we take as the likelihood (evaluation) of node x, P(Yg,,,, | 1:) when observations t; to t; are known to be associable with the time slot in which a: is found. Assume that the observation string with known boundaries is of length T. When each path extension in the separate stacks reaches the length T, the question remains as to how to select the optimal path. If the “highest” stack which contains a path is 5;, we need to select a suficient number of additional nodes in paths of lower stacks to make every surviving path move to the highest stack. What remains in the stacks are partial paths which represent a small subgraph of G. We simply search the subgraph using the standard left-to-right method, the new search problem will be very significantly scaled down with respect to the original problem. Further if I is unacceptably small, further evaluations might be necessary on paths in S 1. The optimal path with the best likelihood is found at the top of the highest stack. . 41 No Wh i=lt0 ] e uate the use Bfifisgfih‘fi? into tackan . ut ex} d ax-l- sta'gt'llx. (if: i‘aamcfil 18%”de }, set length: the order 0? the element start in the path led‘ ‘checking” h initalization: length -—- path_ntax a 0: checkinga-l; variable. length- totalno.ofwordswesearchupmnow -totalno.ofwordsinobsetvanonseq. dfl- total no. of nodes adjacenttostart(stm- -path searching begins) PM," -pathwhichhasbeenscarchedwith “start"asitslastnodc P,- -temperarypathorderisearchedfi'omPM checking- thelabelofthepsth vi-thenodewhichisadjmnttostartinthedigraph Figure 18: A multiple stack decoding algorithm. 42 In a large problem, the subgraph remaining in the stacks after the first partition and search can be further partitioned and searched in a similar manner. This pro- cedure is particularly attractive if the partitioning can be done in real time. The solution would be expected to rapidly converge. Each partition and search involves (Xx/17) or fewer evaluations. 43 4.3 Application Example In [1], an example with relatively few nodes. was provided to keep the resulting graph visually tractable. However, for the purpose of better illustrating the power of the partitioning graph search method, a large planar graph with l, 061 nodes and 1, 196 edges is created in this work for the experiment. The method presented in Section 2.3 for creating a connected planar graph is applied to construct a large graph. The original data file is built by using the random number generator in a C programming library to generate a few “sentences” , each sentence, or equivalently each path in the resulting digraph, consists of 33 — 40 words (nodes). Every word is represented by an integer number created from the random number generator. Note that difi'erent integer numbers represent different words in the sentences. The data file is shown in Appendix A. The resulting digraph (after extracting 119 planarity breaking arcs), say G, is composed of 1, 061 nodes (including one dummy node 0) and 1,196 edges. The nodes of the graph G are shown in Appendix B, and the planarity breaking arcs extracted from the original data file (or, the original graph) are shown in Appendix C. After creating the planar digraph, the next task is to apply the partitioning al- gorithm to. its underlying undirected graph. The main purpose of the partitioning algorithm is to partition the vertices of the planar graph and find the nodes in the C set for evaluation. Therefore, the direction of each edge in the decoding graph G need not to be considered as the partitioning process procedes. The node “0” is chosen to be the reference node for classifying the vertices of G into levels. In this graph, the vertices are partitioned into 58 levels from level 0 to level 57. Using the partitioning algorithm, there are a total of 63 nodes in the C set. These nodes are selected in this graph for evaluation. The position of these selected nodes is shown in Appendix A. Since these “high payoff” nodes have been chosen, let’s further consider how to execute the decoding process. The experiment was carried out as follows: 1. A complete path in the graph was chOsen as the given word string. Of course the word string will be unknown in practice. A path containing 37 nodes was selected to be the symbol string. 2. In order to obviate the construction of 1, 061 word models (since we knew that only 0(\/1V) of them would be used in the search), we trained 81‘ models. These trained model are shown in Appendix D. These models corresponded to the C set nodes found by partitioning, plus a few additional ones (see Appendix A) for a purpose described below. For convenience, the trained models were evaluated in advance with respect to each discrete set of observations representing words in the chosen sentence (correct path). 3. The multiple stack graph search algorithm was used to search for the optimal path. At the end of the search, there were nine stacks created holding 264 candidate paths. This means that the maximum number of the nodes evaluated on a path was nine. The threshold at stack i was given by 2' times the best match score for any given word in the 81 test words to its correct model. After the threshold was set for pruning the unlikely partial paths at each stack, only 38 paths were remained in the stacks (see Appendix E). 4. A second subset of the key nodes from the surviving paths was evaluated (the left-to-right search approach was applied) to move the surviving paths in the lower stacks to Stack 9. An additional node was added to a path by inserting the appropriate model from the the set of 81 trained model. It was necessary to evaluate 18 additional nodes to move the paths in the lower stacks to Stack 45 9. The path which had the best likelihood in Stack 9 was the optimal path. To find a optimal path using the graph partitioning and search method in this graph, 81 nodes are selected for evaluation. Using the conventional left-to-right search to this graph, to evaluate 9 nodes on every path requires 299 node evaluations. The experiment demonstrates that a significant reduction in the number of evaluations is possible with the partitioning procedure with respect to the left-to-right method. In real problems in which a more carefully planned search strategy can be employed, much more improvement than was achieved in this simple example is to be expected. Further, since the partitioning algorithm’s main benefit is in reducing the complexity to 0(\/1V), results will be more significant for very large N. N values of 106 — 1011 nodes are not uncommon, for example, in speech recognition graphs [3], [13]. 46 5 Conclusions and Future Work For signal decoding problems, the graph partitioning method offers a systematic way of locating a very small number of nodes which are guaranteed to give effective cov- erage of a decoding graph. Through the evaluations of this relatively small number of selected nodes, an optimal path for a given observation string can be found. The major contribution of this research is the development of a planar graph par- titioning algorithm, which can be used to select (Xx/N) nodes for evaluation from an N node planar decoding graph. In the process, a method for finding an appro- priate simple cycle separator to complete the vertex partitioning has been developed. When the search is combined with partitioning, the overall graph search complexity is 0(w/17). This represents a steep~ decrease with respect to conventional left-to-right decoding approaches which are usually 0(N). A procedure for circumventing the ap— parent limitationof these W-Planar Separator Theorems to planar graphs is found in [1]. To develop appropriate partitioning algorithms for the more general case will be the subject of future research. Following partitioning, “scattered” nodes are evaluated and the graph is searched and pruned according to a likelihood measure. To provide “fair competition” among the partial paths with different numbers of evaluations requires the use of an un- conventional search algorithm since most existing methods assume the sequential evaluation of nodes from left-to-right. For this purpose, a multiple stack decoding algorithm has been applied to carry out this procedure. In the present research, graph search in the presence of known boundaries in the observation string has been presented. An important issue for future research is the implementation of methods for search with unknown boundaries which is suggested in [1]. Another important issue is the ability to perform in real-time the repartition of the subgraph following a 47 given search. A summary of future work is as follows: 1. An appropriate vertex partitioning algorithm for generally nonplanar graphs will be developed. 2. Strategies for “optimal” multiple partitioning, and recursive partitioning and search, in real time will be developed and evaluated. 3. Graph partitioning and search algorithms will be applied to the problem of continuous speech recognition. The algorithm developed for this search must be applicable to the case of unknown acoustic boundaries. 48 References [1] C.G. Venkatesh, J.R. Deller, Jr., and MB. Cozzens, “A Graph Partitioning Approach to Signal Decoding,” in press Discrete Applied Mathematics (special issue on Graph Theory in Electrical Engineering). . [2] LR. Bahl and F. Jelinek, “Decoding for Channels with Insertions, Deletions and Substitutions with Applications to Speech Recognition,” IEEE Transaction on Information Theory, Vol. IT-21, No.4, pp.404-411, July 1975. [3] L.R. Bahl, F. Jelinek and R..L. Mercer, “A Maximum Likelihood Approach to Continuous Speech Recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI—5, No.2, pp. 179—190, March 1983. [4] R.J Lipton and R..E. Tarjan, “A Separator Theorem For Planar Graphs,” SIAM J. Computing, Vol. 36, No. 2, pp. 177-189, April 1979. [5] G.L. Miller, “Finding small simple cycle separator for 2-connected planar graphs,” Proceedings of the Sixteenth Annual ACM Symposium 0n Theory of Computing, pp. 376-382, April 1984. [6] H. Gazit and G.L. Miller, “A Parallel Algorithm for Finding a Separator. in Pla- nar Graphs,” Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 238-248, 1987. [7] J. Hopcroft and RE. Tarjan, “Efficient Planarity Testing,” J. Assoc. Comput. Mach., Vol. 21, pp. 549—568, 1974. [8] H.N. Djidjev, “On the problem of partitioning planar graphs,” SIAM J. Alg. Discrete Math., Vol 3, No. 2, pp. 229—240, June 1982. [9] J .A. Bondy and U.S.R Murty, Graph Theory with Applications, New York: Amer- ican Elsevier Publishing, 1976. [10] 8. Even, Graph Algorithms, Potomac MD: Computer Science Press, 1979. [11] A. Gibbons, Algorithmic Graph Theory, New York: Cambridge University Press, 1985. [12] J.A. McHugh, Algorithmic Graph Theory, Englewood Cliffs NJ: Prentice-Hall, 1990. [13]. B.T. Lowerre and R. Reddy, “The HARPY Speech Understanding System,” in W.A.Lea (ed.), Trends in Speech Recognition, pp.340—360, Englewood Cliffs NJ: Prentice-Hall, 1980. 49 [14] S. Rao, “Finding Near Optimal Separators in Planar Graphs,” Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 225—237, 1987. [15] R.J. Lipton and RE. Tarjan, “Applications of a Planar Separator Theorem,” Proc. 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 162-170, 1977. [16] J .R. Gilbert, J .P. Hutchinson and RE. Tarjan, “A Separator Theorem for Graphs of Bounded Genus,” Journal of Algorithms, Vol. 5, pp. 391-407, 1984. [17] LR. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” Proc. IEEE, vol. 77, No. 2, pp. 257—285, 1989. [18] RC. Read, “A New Method for Drawing a Planar Graph Given the Cyclic Or- der of the Edges at Each Vertex,” Research Report CORR 86-14, University of Waterloo, July 1986. 50 1716 <-- C 1136 1720 1832 751 1681 1106 1970 <—- C 1693 352 <-- C [SJPI?IEPII)I){.AI 918 1416 <-- C 1488 <-- C 1936 391 <-- C 51 1315 <-- C 1572 1851 1944 1798 <-- C 1094 250 537 i420 546 453 1816 1972 <-- C 1964 1710 290 1012 1310 357 1901 1114 1515 1489 1298 520 1445 <-- C 1904 52 747 <-- C 53 1354 818 1452 <- C 1186 749 1000 1357 1491 1378 101 171 311 1176 54 Next page . 818 1586 4480 6389 63 1452 <-- C 622 3926 61261 1005 1186 1363 1032 2040 1470 749 1569 3329 9144 305 1000 1180 3682 21941 1144 1357 1493 5764 7872 1337 1491 1421 21615 5569 524 1378 326 7961 4972 1935 101 259 9273 5364 133 171 1076 31275 11684 367 311 192 4038 6931 466 1176 26 4923 8423 505 597 <- C 2000 <-- C 5490 7927 1704 585 931 7443 3594 59 566 852 <- C 7837 2182 1592 1963 901 41368 . 745 1661 841 7746 3401 506 19 1482 61469 9868 1579 1983 341 8505 6820 1196 558 1499 <- C . 6538 170 <-- C 1778 1112 9480 3940 742 1499 <- C 1489 6424 6512 378 793 649 6678 91289 744 413 825 81139 9621 680 1303 3387 <- C 9763 7970 <- C 580 <- C 1514 675 31959 3668 1075 1767 848 6707 5693 425 1572 83 6242 4352 1922 739 . 6663 <- 2940 1038 474 2914 3759 9208 1014 1901 8277 6332 8571 1075 1557 3062 3455 3579 1453 . 3631 7685 6821 20 1287 7845 3716 6963 897 658 2380 3136 2724 . 1030 8011 7720 8762 1516 786 1567 5832 51187 235 150 2350 4751 4645 635 1360 5307 <- C 5681 8600 1451 897 3339 5106 6551 368 673 8929 2379 6329 1002 92 9216 9719 7018 1917 25 6479 6381 4975 873 1622 4703 2919 6080 706 609 6999 7163 6964 328 991 9000 4219 54 3606 8225 4212 5046 81547 3377 4891 41425 8659 8367 8252 3954 3074 6685 6519 8387 7043 7923 7200 7317 7723 <-- C 2099 2249 7265 4764 6818 6882 4165 9324 4545 9545 31263 5792 71369 3291 6410 5546 6274 7238 2735 6234 7984 5807 7207 8214 3385 8663 9228 9333 5336 6929 8626 6470 3300 3439 6977 9012 2188 6849 71154 <- C 7834 6330 2868 2809 4544 8190 6551 2673 . 8362 4878 7215 9843 3097 1085 6206 2626 6723 9012 77 17 3800 2701 9088 5310 5325 2508 3310 8922 4357 41617 6479 2876 5653 21901 2831 6740 7238 2546 3114 6512 3807 21127 6453 11515 4220 6297 7816 5307 <-- C 2918 2094 4024 9972 1489 9416 <- C 4750 5290 . 71298 7488 41048 2304 7964 4520 9936 8080 4196 9710 5445 <-- C 4391 21028 6381 7290 7904 81315 5288 7124 2274 3252 71572 2202 2130 2689 7900 61851 7654 6248 7183 2020 . 9851 3518 3618 9798 6415 7176 8168 7630 3094 9079 4908 <—- C 5550 2762 2500 8929 2889 6389 5222 4537 3458 21451 61721 4947 7531 7157 9168 91389 3420 2163 406 5714 4434 51074 8375 3090 4590 7810 8077 3431 2758 4760 9655 41497 9213 2273 9634 3820 9737 7603 8775 . 4739 3055 2594 6058 2697 2984 9160 11401 9122 7140 8006 6068 4824 7936 8202 51273 <-- C 9606 2927 4 92 Next page 55 56 Node 0 8: Node 1 s 914 Node 2 = 827 Node 3 = 302 Node 4 = 1631 Node 5 = 785 Node 6 = 230 Node 7 = 11 Node 8 = 1567 Node 9 = 350 Node 10 = 1307 Node 11: 1339 Node 12 = 929 Node 13 = 1216 Node 14 = 479 Node 15 = 703 Node 16 = 699 Node 17 =- 90 Node 18:- 440 (ABOUT) Node 19= 1926 Node 20:1032 Node 21 = 1329 Node 22 = 1682 Node 23 = 1764 Node 24 = 1615 (ALL) Node 25 = 1961 Node 26 = 1273 Node 27 = 1275 Node 28= 38 (AN ) Node 29= 923 Node 30:: 540 Node 31 = 1443 Node 32 = 1837 Node 33 = 1368 Node 34 = 1746 Node 35 =-- 1469 Node 36 = 505 Node 37 = 1480 Node 38 = 424 Node 39 -- 678 Node-40 = 1139 Node 41 = 1763 Node 42 = 1959 Node 43 = 707 Node 44 a 242 Node 45 = 663 APPENDIX B Node 46 a 1759 Node 47 = 332 Node 48 = 1455 Node 49 = 1685 Node 50 a 1716 (AS) Node 51 = 1136 Node 52 = 1720 Node 53 a 1832 Node 54 = 751 Node 55 a 1681 Node 56 = 1106 Node 57 = 379 Node 58 = 1719 Node 59 = 381 Node 60 = 919 Node 61 = 1163 Node 62 = 219 Node 63 = 639 Node 64 = 1261 Node 65 = 40 Node 66 = 1144 Node 67 = 1941 Node 68 = 1872 Node 69 = 1569 Node 70 = 972 Node 71 = 1364 Node 72 = 1684 Node 73 = 931 Node 74 = 423 Node 75 = 1927 Node 76 = 1594 Node 77 = 182 Node 78 = 1401 Node 79 = 1868 Node 80 -- 680 Node 81 = 538 as 3%: gram) Node 84 a 1289 Node 85- - 1621 Node 86 = 1970 (BEARD) Node 87 = 1668 Node 88 = 1693 Node 89 = 352 (BLACK) Node 90 940 Node 91 = 1208 57 ' Node 120: 1154 Node 92 = 571 Node 93 = 1579 Node 94: 821 ‘ Node 95 = 963 (BUTTONS) Node 96- -- 724 Node 97= 762 Node 98 = 1187 Node 99 = 645 Node 100 = 86 Node 101 = 551 Node 102 = 329 Node 103 = 1018 Node 107: 1157 (CLINGS) Node 108— - 1725 Node 109= 366 (COAT) Node 110 = 1377 Node 111 = 252 . Node 112 = 1317 E) Node 113 = 764 OUR) Node 114 = 545 Node 115 = 1291 SIX) Node 116 = 735 Node 117: 214 IGHT) Node 118 = 1336NINE Node 119- - 1439 ZERO) TRESSES) Node 121= 544(T ART) Node 122: 362 (STOP) Node 123- - 1085 YES) Node 124 = 1717 NW)E Node 125- - 1325 R) Node 126=161( Node 127 = 831 LP Node 128 = 806 RUB UT) Node 129 = 918 (REPEAT) Node 130 = 1416 OCK) Node 131 = 1488 GRANDFAT) Node 132 = 1936 NTER) Node 133 = 391 Node 134 = 448 (M) Node 135 = 1252 Node 136 = 1900 Node 137 = 20 (G) Node 138 - 1618 Node 184 . 1420 Node 230 = 375 Node 139 = 1630 Node 185 = 434 Node 231 =1o45 Node 140 = 272 Node 186 = 1810 Node 232 a 559 Node 141 a 522 Node 187 = 1655 Node 233 =685 SNIN'EI’Y'I’H) Node 142 -- 947 Node 188 = 1820 Node 234 = 192 Node 143 a 1389 Node 189 = 739 Node 235 = 249 Node 144a 1068 A Node 1903984 Node236=165 Node 145 = 590 Node 191 = 6 Node 237 = 572 Node 146 = 476 Node 192 = 212 Node 238 = 274 Node 147 = 1634 (YO Node l93= 1425 Node 239= 1228 Node 148 = 267 Node 194 = 1074 (LONG) Node 240: 470 (OLD) Node 149 = 1140 Node l95= 1043 Node 241 = 188 Node 150 a 822 Node 196= 9920111881190) Node 242:.- 868 Node 151 = 629 Node 197- - 882 Node 243 = 573 Node 152 = 225 Node 198= 1263 Node 244 a. 1343 Node 153 :- 891 Node 199 a 546 Node 245 = 723 Node 154 a 1954 Node 200 = 1984 Node 246 = 1088 Node 155= 387 Node 201 -- 626 Node 247 = 922 Node 156 a 1723 (HIMSEIFNode 202=1012 Node 243 = 1553 Node 157:- 818 Node 203= 330 Node 249: 453 Node 158: 1545 Node 204 = 1215 Node 250: 1816 Node 159 = 641 Node 205 = 701 Node 251 = 1972 (SEVERAL) Node160=234 Node206=310 Node252=1 1964 Node 161 = 1385 Node 207 = 876 Node 253 = 1710 Node 162-977 Node208=1238 Node254=290 Node 163a 1834 Node 209 = 1127 Node 255 = 1124 Node 164: 181 Node 210 = 297 (MY) Node 255 =13o Node 165:878 Node 211 =24 Node 257:243 Node 166 a 206 Node 212 = 1290 Node 253 31176 Node 167 =- 1800 Node 213 a 304 Node 259 -- 908 (STILL) Node 168 a 508 Node 214 = 196 Node 250 -.- 339 Node 169 = 674 Node 215 = 1288 Node 261 -- 1451 Node 170= 1807 Node 216:202 Node 252 -.- 1406 Node 171 = 220 Node 217 =- 1654 Node 263 = 1431 Node 172 = 94 (IN) Node 218 = 415 Node 264 = 1213 Node 173 = 750 Node 219 = 1079 Node 265 = 1603 Node 174 = 1048 Node 220 = 1458 Node 266 = 254 Node 175 =- 80 Node 221 = 1531 Node 267 = 824 Node 176 = 1028 Node 222 = 163 Node 268 = 927 Node l77=1315(IS) Node223=77 Node269=1244 Node 178 = 1851 Node 224 = 147 Node 270 = 1547 Node 179 a 1944 Node 225 = 1737 Node 271 = 367 Node 180= 1798 (KNOW) Node 226: 1055 Node 272: 519 Node 181 . 1094 Node 227= 1160 (NEARLYmode 273- .. 1200 Node 182= 250 Node 228: 68 Node 274a 1265 (SWIFI'LY ) Node 183 a 537 Node 229 =- 1606 Node 275 :3 1324 58 Node 276 =- 1369 Node 322 a 1437 Node 277 = 207 Node 323 = 268 Node 278 = 1333 Node 324 = 1117 Node279=l300 Node325=605 Node 280 = 849 Node 326 = 1982 Node 281 2809 Node 327=559 Node 282 = 1097 Node 328 = 1715 Node 283 = 1310 Node 329 = 1686 Node284=357 Node 330= 125 (WISH) Node 285 = 1901 Node 331 = 1729 Node 286 = 1114 Node 332 = 1622 Node 287 = 1515 Node 333 = 317 Node288=1489 Node 334:300 Node 289 = 1298 Node 335 = 1819 Node 290 = 520 Node 336 = 1581 Node 291 = 1445 (THINKS) Node 337 = 477 Node 292 a 1904 Node 338 = 788 Node 293 = 269 Node 339 a 377 Node294=1183 Node340=1690 Node 295 = 1518 Node 341 = 1598 Node 296 = 168 Node 342 -- 1424 Node 297 = 1550 Node 343 = 1853 Node 298 = 389 Node 344 = 1527 Node 299 = 1721 Node 345 = 1784 Node300=ll68 Node346=729 Node 301 = 1714 Node 347 = 1061 Node302=1090 Node348=1663 Node 303 = 758 Node 349 = 850 Node304=273 Node 350=283 Node 305 -- 775 Node 351 = 1595 Node306=58 Node 352=265 Node307=TO Node353=154(YEARS) Node 308 a: 192 Node 354 = 1522 Node 309 = 1502 Node 355 -- 872 Node 310 = 616 Node 356 = 1841 Node 311= 796 Node 357 = 1647 Node 312 = 861 Node 358 = 601 Node 313 = 458 Node 359 = 1815 Node314=446 Node360=901 Node 315 = 1734 Node 361 = 136 Node 316 = 255 Node 362 = 483 Node 317 a 351 Node 363 = 1919 Node 318 = 8 (USUALLY) Node 364 = 1276 Node 319 a 1534 Node 365 = 1212 Node 320 = 1878 Node 366 = 1610 Node 321 a 1044 (WELL) Node 367 =- 874 59 Node 368 a 36 Node 369 = 1034 Node 370 = 1915 Node 371 = 819 Node 372 = 160 Node 373 = 637 Node 374 = 179 Node 375 = 232 Node 376 = 1987 Node 377 = 1509 as. 333 = % (m Node 380 = 1207 - Node 381 = 747 (YOU) Node 382 = 1825 Node 383 = 460 Node 384 = 1838 Node 385 = 313 Node 386 = 1295 Node 387 = 1757 Node 388 = 1589 Node 389 = 1367 Node 390 = 815 Node 391 = 896 (A) Node 392 = 754 Node 393 = 246 Node 394 = 812 Node 395 = 1925 Node 396 = 141 Node 397 = 759 Node 398 = 1396 Node 401 = 1980 Node 402 = 307 Node 403 = 1962 Node 404 = 169 Node 405 = 568 Node 406 = 1651 Node 407 = 1678 Node 408 = 127 Node 409 = 399 Node 410 = 1855 Node 411 = 587 Node 412 = 237 (B ) Node 413 = 1883 Node 414 =3 346 Node 415 = 1758 Node 416 = 926 Node 417 = 1639 Node 418 = 468 Node 419 = 1172 Node 420 = 451 Node 421 = 745 Node 422 = 592 Node 423 = 1504 Node 424 = 1679 Node 425 a 913 Node 426 = 1732 Node 427= 1659 Node 428= 1694 (C) Node 429= 731 Node 430--- 1741 Node 431 = 614 Node 432 = 382 Node 433 = 1771 Node 434 = 741 Node 435 = 781 Node 436 = 1627 Node 437 = 1680 Node 438 = 1796 Node 439 = 1563 Node 440 = 1906 Node 441 = 306 Node 442 = 832 Node 443 = 1946 Node 444 = 251 Node 445 = 397 Node 446 = 996 Node 447 = 640 Node 448 = 1342 Node 449 = 852 (D) Node 450 = 671 Node 451= 584 Node 452= 682 (E) Node 453= 630 Node 454= 1413 Node 455 = 1921 Node 456 = 1596 Node 457 = 44 Node 458 = 337 Node 459 a 577 Node 460 =1671 Node 461 =17 Node 462 =1948 Node 463 = 1933 Node 464 = 1665 Node465 = 1726 Node 466 2591 Node 467 = 1448 Node 470 = 1619 Node 471 a 1047 Node 472 = 611 Node 473 = 1899 Node 474 = 1236 Node 475 = 835 Node 476 = 1415 Node 477 = 1817 Node 478 = 1730 Node 479 = 1688 Node 480 = 85 (F) Node 481 = 102 Node 482 2 456 Node 483 = 108 Node 484 = 471 Node 485 = 756 Node 486 = 1928 Node 487 = 773 Node 488 = 1348 (G) Node 489: 221 Node 490= 1268 Node 491 = 1885 Node 492 = 1240 Node 493 = 1524 Node 494 = 1319 Node 495 = 1570 Node 496 = 1486 Node504=23 Node505=21 Node 506 = 1649 Node 507 = 1958 Node 508 = 946 (H) Node 509 = 1241 Node 510 =1483 Node 511 = 617 Node 512 = 1093 Node 513 = 1988 Node 514 = 187 Node 515 = 82 Node 516 = 944 Node 517 = 1086 Node 518 = 1943 Node 519 = 1870 Node 520= 1323 Node 521_ = 1492 Node 536: - 846 Node 539 = 928 Node 540 = 1272 Node 541 = 1739 Node 542 = 1223 Node 543 = 1142 Node 544 = 1062 Node 545 = 1703 Node 546 = 502 Node 547 = 547 Node 548 = 1057 Node 549 = 865 Node 550 = 473 Node 551 = 28 Node 552 a 909 Node 553 = 1371 Node 554 = 1808 Node 555 = 436 Node 556 =- 1280 Node 557 -- 491 Node 558 = 1811 Node 559 = 100 Node 560 = 416 Node 561 = 1890 Node 562 = 138 Node 563 = 218 Node 564 s 439(1) Node 565 = 1491 Node 566 a 178 Node 567 = 19 Node 571 = 1041 (K) Node 572 = 447 Node 574 =- 450 Node 575 = 1312 Node 576 = 811 Node 577 = 830 Node 578 = 573 Node 579 a 1585 Node 580 = 331 Node 581 = 1745 Node 582 = 990 Node 583 = 1611 Node 584 = 63 Node 585 = 1005 Node 586 = 1470 Node 587 = 305 Node 588 = 1337 Node 589 = 524 Node 590 = 1935 Node 591 = 133 Node 595 = 1592 Node 596 = 1196 Node 597 =- 170 (L) Node 598 = 742 Node 599 = 378 Node 600 = 744 Node 601 = 1075 Node 608 = 1516 Node 609 = 235 Node 610 = 635 Node 611 = 368 Node 612 = 1002 Node 613 = 1917 Node 614 = 873 Node 615 = 706 Node 616 = 328 Node 617 = 1452 (M) Node 618 = 1186 Node 619 = 749 Node 620 a 1000 Node 621 = 1357 Node 622 = 1378 Node 623 = 101 Node 624 = 171 Node 625 = 311 Node 626 = 597 (N) Node 627 = 585 Node 628 = 566 Node 629 = 1963 Node 630 = 1661 Node 631 = 1983 Node 632 = 558 Node 633 = 1778 Node 634 = 1499 (0) Node 635 = 413 Node 636 = 1303 Node 637 = 1514 Node 638 = 1767 Node 639 = 474 Node 640 = 1557 Node 641 = 1287 Node 642 = 658 Node 643 = 1030 61 Node 644 a 786 Node 645 = 150 Node 646 = 1360 Node 647 = 92 Node 648 = 25 Node 649 -- 609 Node 650 = 1586 Node 651 = 622 Node 652 = 1363 Node 653 = 1180 Node 654 = 1493 Node 655 = 1421 Node 656 = 326 Node 657 = 259 Node 666 = 25 Node 667 =3387 (Q) Node 668 = 675 Node 669 = 848 Node 670 = 83 Node 671 = 2914 Node 672 = 8277 Node 673 = 3062 Node 674 = 3631 Node 675 = 7845 Node 676 = 2380 Node 677 = 8011 Node 678 = 2350 Node 679 = 5307 (R) Node 680 = 3339 Node 681 = 8929 Node 682 = 9216 Node 683 = 6479 Node 684 = 4703 Node 685 = 6999 Node 686 = 9000 Node 687 = 4480 Node 688 = 3926 Node 689 = 3329 Node 690 = 3682 Node 691 =- 5764 Node 692 -—- 21615 Node 693 = 7961 Node 694 = 9273 Node 695 = 31275 Node 696 = 4038 Node 697 = 4923 Node 698 = 5490 Node 699 = 7443 Node 700 = 7837 Node 701 = 41368 Node-702 = 7746 Node 703 a 61469 Node 704 = 8505 Node 705 = 9480 Node 706 = 6424 Node 707 = 6678 Node 708 = 81139 Node 709 = 9763 Node 710 = 31959 Node 711 a 6707 Node 712 = 6242 Node 713 = 6663 (S) Node 714 = 3759 Node 715 = 6332 Node 716 =- 3455 Node 717 = 7685 Node 718 = 3716 Node 719 = 3136 Node 720 = 7720 Node 721 = 5832 Node 722 = 4751 Node 723 = 5681 Node 724 = 5106 Node 725 = 2379 Node 726 = 9719 Node 727 = 6381 Node 728 = 2919 Node 729 = 7163 Node 730 = 4219 Node 731 = 6389 Node 732 = 61261 Node 733 = 2040 Node 734 = 9144 Node 735 =- 21941 Node 736 = 7872 Node 737 = 5569 Node 738 = 4972 Node 739 = 5364 Node 740 =11684 Node 741 = 6931 Node 742 = 8423 Node 743 = 7927 Node 744 = 3594 Node 745 = 2182 Node 746 = 3401 Node 747 = 9868 Node 748 = 6820 Node 749 = 6538 Node 750 = 3940 Node 751 = 6512 Node 752 = 91289 Node 753 = 9621 Node 754 = 7970 ('1') Node 755 = 3668 Node 756 = 5693 Node 757 = 4352 Node 758 -- 2940 Node 759 = 9208 Node 760 = 8571 Node 761 = 3579 Node 762 =-- 6821 Node 763 = 6963 Node 764 = 2724 Node 765 = 8762 Node 766 = 51187 Node 767 = 4645 Node 768 = 8600 Node 769 = 6551 Node 770 = 6329 Node 771 = 7018 Node 772 = 4975 Node 773 = 6080 Node 774 = 6964 Node 775 = 7157 Node 776 = 7572 Node 779 = 8252 Node 780 = 7317 Node 781 a 4764 62 Node 782 = 4545 Node 783 = 3291 Node 784 = 2735 Node 785 = 8214 Node 786 = 5336 Node 787 = 3439 Node 788 = 71154 (U) Node 789 = 4544 Node 790 = 8362 Node 791 = 7717 Node 792 = 5325 Node 793 = 41617 Node 794 = 2831 Node 795 = 4806 Node 796 = 2918 Node 804 = 2020 Node 805 = 3618 Node 806 = 7630 Node 807 = 2762 Node 808 = 5222 Node 809 = 4947 Node 810 = 91389 Node 811 = 5068 Node 812 = 4590 Node 813 = 4760 Node 814 = 9634 Node 815 = 2697 Node 816 = 7140 Node 817 = 8202 Node 818 = 8629 Node 819 = 8225 Node 820 = 4891 Node 821 = 3954 Node 822 = 8387 Node 823 = 7723 (W) Node 824 = 6818 Node 825 = 9545 Node 826 = 6410 Node 827 = 6234 Node 828 a 3385 Node 829 = 6929 Node 830 = 6977 Node 831 = 7834 Node 832 a 8190 Node 833 = 4878 Node 834 = 6206 Node 835 -- 3800 Node 836 = 2508 Node 837 = 6740 Node 838 = 3807 Node 839 = 4220 Node 840 = 2094 Node 841 = 4750 Node 842 = 41048 Node 843 = 8080 Node 844 = 21028 Node 845 = 81315 Node 846 = 71572 Node 847 = 61851 Node 848 = 9944 Node 849 = 9798 Node 850 = 3094 Node 851 = 2500 Node 852 = 4537 Node 853 = 3420 Node 854 = 4434 Node 855 = 7810 Node 856 = 9655 Node 857 = 3820 Node 858 = 4739 Node 859 = 2984 Node 860 = 8006 Node 861 = 51273 (X) Node 862 = 4214 Node 863 = 4212 Node 864 = 41425 Node 865 = 3074 Node 866 = 7043 Node 867 = 2099 Node 868 = 6882 Node 869 = 31263 Node 870 = 5546 Node 871 = 7984 Node 872 = 8663 Node 873 = 8626 Node 874 = 9012 Node 875 = 6330 Node 876 = 7215 Node 877 = 2626 Node 878 -- 2701 Node 879 = 3310 Node 880 = 2876 Node 881 = 7238 Node 882 = 21127 Node 883 = 6297 Node 884 = 4024 Node 885 = 5290 Node 886 = 2304 Node 887 = 4196 Node 888 = 5288 Node 889 = 2202 Node 890 = 7654 Node 891 = 6415 Node 892 = 9079 Node 893 = 3458 Node 894 = 7531 Node 895 = 2163 Node 896 = 51074 Node 897 = 8077 Node 898 = 41497 Node 899 = 9737 Node 900 = 3055 Node 901 = 9160 Node 902 = 6068 Node 903 = 9606 Node 904 = 6375 Node 905 = 5046 Node 906 = 8659 Node 907 = 6685 Node 908 = 7923 Node 909 = 2249 Node 910 = 4165 Node 911 = 5792 Node 912 = 6274 Node 913 = 5807 Node 914 = 9228 Node 915 = 6470 Node 916 = 2188 Node 917 = 2868 Node 918 = 2673 Node 919 = 9843 C 63 Node 920 = 6723 Node 921 = 9088 Node 922 = 8922 Node 923 = 5653 Node 924 = 2546 Node 925 = 6453 Node 926 = 7816 Node 927 = 9972 Node 928 = 7964 Node 929 = 9710 Node 930 = 7290 Node 931 = 7124 Node 932 = 2130 Node 933 = 6248 Node 934 = 9851 Node 935 = 7176 Node 936 = 4908 (Y) Node 937 = 2889 Node 938 = 21451 Node 939 = 3406 Node 942 = 9213 Node 943 = 7603 Node 944 = 2594 Node 949 = 81547 Node 950 = 8367 Node 951 = 6519 Node 952 = 7200 Node 953 = 7265 Node 954 = 9324 Node 955 =-- 71369 Node 956 = 7207 Node 957 = 9333 Node 958 = 3300 Node 959 = 6849 Node 960 = 2809 Node 961 = 3097 Node 962 = 5310 Node 963 = 4357 Node 964 = 21901 Node 965 = 3114 Node 966 = 11515 Node 967 = 71298 Node 968 = 4520 Node969=5445(2) Node 970 = 7904 Node 971 = 2274 Node 972 = 2689 Node 973 = 7183 Node 974 = 3518 Node 975 = 8168 Node 976 -- 5550 Node 977 = 61721 Node 978 = 9168 Node 979 = 5714 Node 980 = 3090 Node 981 = 2758 Node 982 = 2273 Node 983 = 8775 Node 984 = 6058 Node 985 = 9122 Node 986 = 7936 Node 987 s 4192 Node 988 = 9502 Node 989 = 2929 Node 990 = 2616 Node 991 = 2796 Node 992 = 6861 Node 993 = 4558 Node 997 Q 6351 Node 998 = 51248 (ONE) Node 999 = 8876 Node 1000 = 3534 Node 1001 = 9878 Node 1002 = 7044 Node 1003 = 5437 Node 1004 = 6268 Node 1005 = 5117 Node 1006 = 4605 Node 1007 = 41982 Node 1008 = 4559 Node 1009 = 3715 Node 1010 = 4255 Node 1011 = 9686 Node 1012 = 6125 Node 1013 = 9729 Node 1014 = 7622 Node 1015 = 3117 Node 1016 = 8300 Node 1017 = 9123 Node 1018 = 9819 Node 1019 = 7581 Node 1020 = 2477 Node 1021 = 8788 Node 1022 = 8377 Node 1023 = 5690 Node 1024 = 5598 Node 1025 = 3424 Node 1026 = 7853 Node 1027 = 9527 Node 1028 = 9784 Node 1029 = 6729 Node 1030 = 3061 Node 1031 = 9663 Node 1032 = 31925 Node 1033 = 4850 (TWO) Node 1034 = 2283 Node 1035 = 21595 Node 1036 = 4265 Node 1037 = 6154 Node 1038 = 9522 Node 1039 = 4872 Node 1040 = 5841 Node 1041 = 5647 Node 1042 = 4601 Node 1043 = 9815 Node 1044 = 5964 Node 1045 = 2901 Node 1046 = 7090 Node 1047 = 2136 Node 1048 = 3483 Node 1049 = 5919 Node 1050 = 7276 Node 1051 = 5212 Node 1052 = 11610 Node 1053 = 2874 Node 1054 = 2036 Node 1055 = 5034 Node 1056 = 7079 Node 1057 =- 7915 Node 1058 = 4819 Node 1059 = 2160 Node 1060 = 5977 APPENDIX C P1anarity_brealcing_arcs = from node 203 to 101 Planarity_breaking_arcs = from node 204 to 201 P1anarity_breaking_arcs = from node 222 to 194 Planarity_breaking_arcs = from node 238 to 170 Planarity_brea|cing_arcs = from node 248 to 199 P1anarity_breaking_arcs = from node 262 to 230 Planarity_breaking_arcs = from node 276 to 208 Planarity_breaking_arcs = from node 287 to 10 P1anarity__breaking_arcs = from node 292 to 238 P1anarity_breaking_arcs = from node 318 to 207 Planarity_breaking_arcs = from node 328 to 316 Planarity_b1ealdng_arcs = from node 334 to 29 Planarity_breaking_arcs = from node 348 to 330 Planarity_brealdng_arcs = from node 351 to 170 Planarity_breaking_arcs = from node 359 to 252 Planarity_breaking_arcs = from node 360 to 302 Planarity_breaking_arcs = from node 369 to 219 Planarity_breaking_arcs = from node 372 to 162 P1anarity_breaking_arcs = from node 374 to 324 Planarity_breaking_arcs = from node 376 to 315 'Planarity_brealdng_arcs = from node 315 to 189 Planarity_breaking_arcs = from node 379 to 377 P1anarity_breaking_arcs = from node 388 to 168 Planarity_brea.king_arcs = from node 395 to 303 Planarity_breaking_arcs = from node 412 to 404 P1anarity_breaking_arcs = from node 415 to 133 P1anarity_breaking_arcs = from node 133 to 301 Planarity_breaking_arcs = from node 421 to 350 Planarity_breaking_arcs = from node 427 to 108 Planarity_breaking_ams = from node 437 to 103 P1anarity_breaking_arcs = from node 441 to 263 Planarity_breaking_arcs = from node 444 to 284 Planarity_breaking_arcs = from node 450 to 316 P1anarity_breaking_arcs = from node 452 to 374 Planarity_breaking_arcs = from node 456 to 438 P1anarity_breaking_arcs = from node 462 to 335 P1anarity_breaking_arcs = from node 468 to 183 Planarity_b1ealdng_arcs = from node 472 to 151 Planarity_breaking_arcs = from node 473 to 147 P1anarity_brealcing_arcs = from node 475 to 333 Planarity_breaking_arcs = from node 479 to 454 P1anarity__bneaking_ams = from node 454 to 320 Planarity_b1ealdng_arcs = from node 486 to 485 P1anarity_breaking_ams = from node 487 to 191 P1anarity_breaking_arcs -- from node 491 to 140 65 P1anarity_breaking_arcs = from node 494 to 178 P1anarity_breaking_arcs = from node 17 8 to 36 Planarity_breaking_arcs = from node 496 to 430 Planarity_breaking_arcs = from node 498 to 377 Planarity_b1eaking_arcs = from node 0 to 491 Planarity_breaking_ares = from node 500 to 23 Planarity_breaking_arcs = from node 23 to 147 Planarity.breaking_arcs = from node 501 to 237 Planarity_breaking_arcs = from node 503 to 437 P1anarity_breaking_arcs = from node 505 to 249 Planarity_breaking_arcs = from node 249 to 59 Planarity_breaking_arcs = from node 59 to 299 Planarity_breaking_arcs = from node 299 to 169 Planarity_brealdng_arcs = from node 514 to 73 Planarity_breaking_arcs = from node 522 to 119 P1anarity_brealdng_arcs = from node 0 to 19 Planarity_breaking_a1cs = from node 529 to 452 Planarity_breaking_arcs = from node 530 to 354 Planarity_breaking_arcs = from node 533 to 395 Planarity_breaking_ares = from node 534 to 322 Planarity_breaking_arcs = from node 544 to 144 P1anarity_brealdng_arcs = from node 553 to 387 Planarity_breaking_arcs = from node 560 to 333 Planarity_breaking_arcs = from node 562 to 287 Planarity_breaking_arcs = from node 564 to 311 Planarity_breaking_arcs = from node 579 to 216 P1anarity_breaking_arcs = from node 583 to 412 Planarity_breaking_arcs = from node 587 to 66 Planarity_brealcing_arcs = from node 591 to 271 Planarity_breaking_a1cs = from node 592 to 36 P1anarity_breaking_arcs = from node 595 to 421 Planarity_breaking_arcs = from node 421 to 534 P1anarity_breaking_arcs = from node 534 to 93 Planarity_breaking_arcs = from node 600 to 80 P1anarity_breaking_arcs = from node 80 to 379 Planarity_breaking_arcs = from node 605 to 601 Planarity_breaking_arcs = from node 606 to 137 P1anarity_breaking_arcs = from node 610 to 261 P1anarity_breaking_arcs = from node 616 to 157 Planarity_breaking_arcs = from node 621 to 565 P1anarity_breaking_arcs = from node 625 to 258 P1anarity_breaking_arcs = from node 630 to 567 Planarity_breaking_arcs = from node 634 to 501 Planarity_breaking_arcs = from node 638 to 108 P1anarity_breaking_arcs = from node 108 to 189 Planarity_breaking_arcs = from node 639 to 285 P1anarity_breaking_a1cs =- from node 646 to 607 Planarity_breaking_arcs = from node 607 to 243 P1anarity_breaking_arcs = from node 648 to 332 Planarity_breaking_arcs = from node 649 to 528 P1anarity_breaking_arcs = from node 652 to 69 Planarity_breaking_arcs = from node 658 to 308 Planarity_breaking_arcs = from node 660 to 73 Planarity_breaking_arcs = from node 73 to 449 Planarity_brealdng_arcs = from node 449 to 360 P1anarity_breaking_arcs = from node 663 to 634 P1anan'ty_breaking_arcs = from node 664 to 288 P1anarity_breaking_arcs = from node 677 to 8 Planarity_brealdng_arcs = from node 688 to 20 Planarity_breaking_arcs = from node 790 to 123 Planarity_breaking_ancs = from node 794 to 751 Planarity_breaking_arcs = from node 836 to 683 Planarity_breaking_arcs = from node 875 to 769 Planarity_breaking_arcs = from node 887 to 727 Planarity_breaking_arcs a from node 892 to 681 Planarity_breaking_arcs = from node 938 to 775 Planarity_breaking_arcs = from node 955 to 881 Planarity_breaking_arcs = from node 961 to 874 P1anarity_breaking_arcs = from node 966 to 679 P1anarity_breaking_arcs = from node 679 to 288 Planarity_breaking_arcs = from node 976 to 731 P1anarity_breaking_a1cs = from node 987 to 760 Planarity_breaking_arcs a from node 760 to 958 P1anarity_breaking_arcs = from node 1035 to 913 67 APPENDIX D ABOUT BEARD BLACK BUTTONS CLINGS COAT DRESSES EVER FROCK ' GRANDFAT mm KNOW LONG MISSING NEARLY OLD SEVERAL STILL SWIP'I'LY USUALLY WISH mommcnw>< 23g 68 3 ON