A. Kazmierczak
Oklahoma City University
artk@okcu.edu

Abstract

A rectangular mesh is a rectangular array of processors.  A new algorithm is presented to recognize a rectangular mesh. A program was written to determine if the new mesh recognition algorithm mesh is valid.  The program was written in C and tested using a representation of a network's nodes and their neighbors.  The program tests several meshes of different dimensions and different mesh-like structures.  The program found the meshes and rejected the non-meshes on the test data. The algorithm presented here is fairly simple and straightforward.  However, its true importance lies in the fact that it forms the foundation for algorithms for recognition of more complex mesh like structures, such as, ring mesh, torus, spheroid, ellipsoid, and 3-dimensional mesh. 

1. Introduction

K.V.S. Ramarao [1] presented the problem of recognizing networks.  Networks recognized were bipartite graphs, complete graphs, rings, stars, or trees.  This problem was explored for two reason: because a considerable number of different algorithms were being designed for use on networks,  and because it was expensive to create and use many different algorithms for these networks.  It was worth the investment of time and money to characterize the network structure before using an algorithm, because the cost of an algorithm for an individual network is less expensive than algorithms for general networks.  The cost to determine the type of network plus the cost of an individual algorithm is less than the cost of a general algorithm [1]. 

Recognition algorithms were later developed to find outerplanar graphs [2], strict 2-threshold graphs [3], graphs with threshold of dimension-of-two [4], bipartite-permutation graphs [5], tree connected meshes [6] and mesh networks.  The previous mesh recognition algorithm was presented in  [7].  The algorithm in [7] worked its way around the perimeter of the rectangle assigning coordinates to the nodes of the mesh.

The new mesh recognition algorithm recognizes mesh networks just as the algorithm in [7], but uses a different technique.  The algorithm presented here proceeds back and forth across the rows of the mesh using a coloring scheme and assigning coordinates to the nodes.

2. Related Works

Much of the work related to graph recognition comes from the graph isomorphism problem. “The graph isomorphism problem can be easily stated: check to see if two graphs that look differently are actually the same. Many sub-disciplines of mathematics, such as topology theory and group theory, can be brought to bear on the problem, and yet only for special classes of graphs have polynomial time algorithms been discovered” [8]. The problem of mesh recognition is a restricted case of the more general graph isomorphism problem.

A mesh is defined as a rectangular array of nodes. Any structure that appears like a mesh but is not a mesh is referred to as a mesh-like structure. A mesh-like structure is a structure that is not graph isomorphic to a mesh. One of the first works in this area is due to Hopcroft and Wong [9] who provided the first linear time algorithm for isomorphism of planar graphs. This lead to a great many other studies on graph isomorphism and the complexity of  graph isomorphism from a variety of approaches.. Many works focused on algorithms for graph isomorphism, such as Faizullin & Prolubnikov [10], Kikina & Faizullin [11], Faizullin & Prolubnikov [12] Schmidt & Druffel [13] Gazit & Reif [14] and Wolter, Woo & Volz [17]. Other researchers have addressed the complexity of graph isomorphism, Toda [15], Boucher & Loker [16], Toran [18] and Golubchik [20, 21]. Many works on practically all aspects of graph isomorphism can be found in Bengoetxea [29] and the references therein.

3. Statement of the Problem

The statement of the problem can be stated as: given a mesh looking structure, devise an algorithm to test whether the structure is graph isomorphic to a mesh.

Necessary Conditions.  - All mesh nodes must have two, three or four neighbors (degree of 2, 3 or 4).  Let D₂ denote the number of nodes with two neighbors, D₃ the number of nodes with three neighbors, and D₄ the number of nodes with four neighbors.  Let N denote the number of nodes in this network and let m and n denote the number of columns and rows, respectively.  D₂, D₃, D₄, and N are determined first.  Then m, which must be a positive integer, is calculated as:

A mesh-looking structure has two, not necessarily distinct, positive integer solutions to this equation.   If the following equations hold, the structure might be a mesh:

Fig. 1 shows a structure that meets these necessary conditions and is a rectangular mesh.  By studying the graph, it can be observed that the necessary conditions hold.

 Fig. 2 shows a structure that meets the necessary conditions, but is not a rectangular mesh.

Sufficient Condition.  - An (m ´ n) mesh-looking structure is a mesh if  for every two adjacent nodes  the following equation is true.

r₁ and c₁ are the coordinates of one node and r₂ and c₂ are the coordinates of the adjacent node [7].

A mesh can now be defined as any structure that meets the necessary and sufficient conditions.

4. Informal Description of the Agorithm

The algorithm consists of two phases.  In the first phase, the necessary conditions for a network to be a mesh are verified. If these conditions are met, the second phase peels the mesh row by row, using a coloring scheme as a guide.  During this phase, nodes are assigned coordinates.  A successful assignment of coordinates, which satisfies the sufficient condition, ensures the recognition of a mesh.  The algorithm rejects any other structure.

Phase I. During phase I of the algorithm, the following tasks are performed:

                × Compute values for D₂, D₃, D₄, N, m, and n.

                × Check necessary conditions

                × Select a node with two neighbors to initiate phase II

                                                        . Color all nodes white

                                                         . Set row = 0, column = 0

This phase determines the values of the network parameters D₂, D₃, D₄, and N.  The network parameters are initialized to zero before starting.  As each node is encountered, the appropriate parameter is updated.  After the last node is reached, the network parameters are used to verify the necessary conditions.  If any condition is violated, the algorithm terminates indicating the network is not a mesh.  Otherwise, 2-degree node is selected to initiate the second phase of the algorithm.  Thus, at the conclusion of phase I, necessary conditions have been verified and the structure is mesh-looking.  

Phase II. Phase II of the algorithm assigns coordinates to the nodes and determines if the network is a mesh.  There are many stages, each processing one row of the mesh.  Three algorithms are needed.  The first and last rows have boundary conditions that must be tested, so separate algorithms are necessary.  All internal rows are processed the same way, so one general algorithm is needed.  A coloring scheme is used to guide the processing along the row.  As the nodes are colored, the colors of adjacent nodes must satisfy specific coloring requirements for the network to be a mesh. These requirements are also verified.  The network is rejected as not being a mesh as soon as any requirement is violated.  As a final test, the sufficient condition is verified using the coordinates assigned to each node. If the sufficient conditions are verified, the structure is a mesh.

4.1 Processing the First Row: Algorithm Firstrow

The start node is a node with only two neighbors. Reference Figs 3. This node, called S₁(a₁)._, is then colored black.   The row and column coordinates are set to zero so the coordinates of  S₁(a₁).  are (0, 0).  The subscripts are used to indicate row and column. The subscript for S is the row number and the subscript for a is the column number of the current node being processed. One of S₁(a₁)'s neighbors is colored green.    The white neighbors of the green node are changed to yellow.  The white neighbor of S₁(a₁).  is the next node to be processed.  This is S­₁(a₂)

Find S₁(a₁)

Color S₁(a₁) black

Set row= 1

Assign coordinates (row, column)

Color one of S₁(a₁)'s neighbors to green

Color both green nodes white neighbors to yellow

Change process to S₁(a₁)'s white neighbor node and name it S­₁(a₂)

Node S­₁(a₂) has neighbors that are colored black, yellow, and white.  If this coloring requirement is not true, this is not a rectangle mesh and processing is stopped.  Otherwise, node S­₁(a₂) is colored black.  The column coordinate is incremented by one and the row coordinate remains zero and the node is assigned coordinates (row, column).  The yellow neighbor is colored green.  The white neighbors of the new green node are changed to yellow.  The white neighbor of S₁(a₂) is the next node to be processed.  This node becomes S­₁(a₃)_.

              If  S­₁(a_i)'s  neighbor nodes are black, yellow and white

      Do while S­₁(a_i)'s neighbor nodes are black, yellow, and white

     Color S­₁(a_i) black

     Increment column by one

     Assign coordinates (row, column)

     Color S­₁(a_i)'s yellow neighbor node to green

     Color new green nodes white neighbors to yellow

        Change process to S­₁(a_i)'s white neighbor node and name it S­₁(a_i+1)

Else terminate with failure

The processing performed at node S­₁(a_i+1) is exactly the same as the processing performed at node S­₁(a_i)_.  This same processing continues until the last node on the row S­₁(a_n) is encountered.  Its neighbors colors are black and yellow.  Node S­₁(a_n) is processed the similar to S­₁(a_n-1) except for the assignment of the next node to be processed. 

The first row has now been successfully processed.  To process the next row, return to node S₁(a₁), then to the green neighbor of S₁(a₁).  This is S₂(a₁), the start node of the second row.

If S­₁(a_n)'s neighbors are black and yellow

Color S­₁(a_n) black

Increment column by one

Assign coordinates (row, column)

Color S­₁(a_n)'s  yellow neighbor node to green

Color new green nodes white neighbors to yellow

Change process to green neighbor node of S₁(a₁) and call it S₂(a₁)

                Else terminate with failure

4.2 Processing a Middle Row: Algorithm Middlerow

This section describes the processing for an arbitrary row i, 1 < i < n.

The start node S_i(a₁) has neighbors colored black, green, and yellow.  Reference Figs 4. The color of S_i(a₁) is changed to black. The row coordinate is incremented by one and the column coordinate is set to zero.  The neighbor of S­_i(a₁) that is green is the next node to be processed.  This is  S­i(a₂).  The neighbor of S_i(a₁) that is yellow is colored green.  The white neighbors of this green node are changed to yellow.  Processing proceeds to node S­_i(a₂).

Node S­_i(a₂) has neighbors that are black, black, green, and yellow.  Node S­_i(a₂) is then colored black, the column coordinate is incremented by one, the node is assigned the coordinates (row, column).  The green neighbor of S­_i(a₂) will be the next node processed.  The yellow neighbor of node S­_i(a₂) is colored green.  The white neighbors of this green node are colored yellow.  Processing proceeds to node S­_i(a₃).

The processing performed at node S­_i(a₃) is the same as performed at node S­_i(a₂). Processing continues until node S­_i(a_n) is encountered that has neighbors colored black, black, and yellow.  Node S­_i(a_n) is the last node on this row.  This completes the processing for this row.  To process the next row, return to node S_i(a₁).  The green neighbor of S_i(a₁) is the first node of the next row.  This becomes S_i+1(a₁).  Processing proceeds to S_i+1(a₁).

If  S_i(a₁)'s  neighbor nodes are black, yellow and green

      Do while S_i(a₁)'s neighbor nodes are black, green, and yellow

         Middle Rows           

           Beginning of Middle Row              

    Set S_i(a₁)'s  to black

   Increment row by one

   Set column to zero

   Assign coordinates (row, column)

   Set next process node to S_i(a₁)'s green neighbor node

   Color S_i(a₁)'s  yellow neighbor node to green           

   Color the new green nodes white neighbors to  yellow

   Change process to node S­_i(a₂)

Middle node of Middle Row

 Do while S­_i(a_i)’s neighbor nodes are black, black, green, and yellow

Set S­_i(a_i)  to black

Increment column by one

Assign coordinates (row, column)

Set next process node to S­_i(a_i)'s green neighbor node

Color S­_i(a_i)'s  yellow neighbor node to green        

Color the new green nodes white neighbors to yellow

Change process to next node _S­i(a_i+1)

Last of Middle Row

  If S­_i(a_n)neighbor nodes are black, black, and yellow

Set S­_i(a_n) to black

Increment column by one

Assign coordinates (row, column)

Set next process node to S­_i(a_n)’s green neighbor node named S­_i+1(a₁)

Color S­_i(a_n)'s yellow neighbor to green          

Color the new green nodes white neighbors to yellow

Change process to node S­_i+1(a₁)

                                                Else terminate with failure

                                                Else terminate with failure

4.3 Processing the Last Row: Algorithm Lastrow

The start node for the last row, node S_n(a₁) has neighbors colored black and green. Reference Figs. 5. Node S_n(a₁) is colored black. The row coordinate is incremented by one, the column coordinate is set to zero and the node is assigned coordinates (row, column).  The green neighbor will be the next node on this row.  This becomes node S­_n(a₂), and  processing proceeds to node S­_n(a₂).

          If S­_n(a₁)'s neighbor nodes are black and green

Set S­_n(a₁)  to black

Increment row by one

Set column to zero

Assign coordinates (row, column)

Set next process node to S­_n(a₁₎'s green neighbor node

Change process to node S­_n(a₂)

Else terminate with failure

Node S­_n(a₂) has neighbors colored black, black, and green.  Node S­_n(a₂) is colored black, the column coordinate is incremented by one and the node is assigned coordinates (row, column).  The neighbor colored green will be the next node on the row.  This becomes node S­_n(a₃).  Processing proceeds to this node S­_n(a₃).

If  S­_n(a_i)'s   neighbor nodes are black, black and green

      While S­_n(a_i)'s neighbor nodes are black, black and green

   Set S­_n(a_i) to black

   Increment column by one

   Assign coordinates (row, column)

   Set next process node to S­_n(a_i)'s green neighbor node

 Change process to node S­_n(a_i+1)

                                Else terminate with failure

Node S­_n(a₂) has neighbors colored black, black, and green.  The processing performed at node S­_n(a₂) is the same as performed at node S­_n(a₁).  This same processing continues until some node S­_n(a_n) is encountered that has neighbors colored black and black. 

Node S­_n(a_n) is the last node on the row, and the last node in the mesh.  Node S­_n(a_n) is colored black. The column coordinate is incremented and the node assigned coordinates (row, column). At this point the last row, and the entire mesh, has been successfully processed. Processing can return to the start node of the first row, where the algorithm tests the sufficient condition.  If the sufficient condition does not hold, then there is not a rectangular mesh.  If the sufficient condition holds, then the algorithm will terminate with the successful recognition of a rectangular mesh.

If S­_n(a_n)'s neighbor nodes are black and black

Set S­_n(a_n) to black

Increment column by one

           Assign coordinates (row, column)

                       If coordinates  match sufficient condition

                               Terminate with success

                               Else terminate with failure

              Else terminate with failure
 

4.4 Special Mesh Structures

Degenerate Mesh. - A degenerate mesh is defined as a mesh with only two rows, that is, n = 2. It is distinguished by having nodes with only two or three neighbors; there are no four-degree nodes. The changes to the algorithms are described in very general terms.

The start node chooses its two-degree neighbor to be colored green and chooses its 3-degree neighbor to be the next node to be processed on the row, node a₁. Node a₁ and all other nodes on the row perform the same processing as described in the original algorithm.

In the case of a degenerate mesh, after the first row is processed, processing proceeds to the last row. Thus, recognition of a degenerate mesh requires one application of algorithm FirstRow and one application of algorithm LastRow.

 Special Mesh. - A special mesh is defined as a mesh with only three columns.  The only change to the description in the previous sections is that node a_n is encountered immediately after node a₁; that is, there is no node a₂ between a₁ and a_n.  All other processing is the same.

5. Complexity

In this section we provide an argument for the complexity of the mesh recognition algorithm.

Theorem: The algorithm to recognize a rectangular mesh runs in O(n).

Argument: For the argument, we will count the number of operations performed at a 'typical' node. As a 'typical' node, we select any 4-degree node in the center of the mesh. The operations we count are: 'move' processing from one node to the next, 'find' a neighbor of a node, 'color' the neighbor of a node, and 'check' the color of a neighbor of a node as these are the operations actually performed.

Arbitrarily select a 4-degree node somewhere in the middle of the mesh (the node with coordinates 1,1 will do). Start by 'moving' (1 operation) processing to the green neighbor. From here, the green node 'finds' its four neighbors (4 operations) and 'checks their color (4 operations) for the color pattern. The green node 'colors' itself black (1 operation). The algorithm 'finds' the yellow neighbor (1 operation) and 'colors it green (1 operation). This green node must 'find' its white neighbor from its other three neighbors (3 operations) and 'colors' the node yellow (1 operation). Processing 'moves' back to the newly colored black node (1 operation).  Processing is now done for this arbitrary 4-degree node. The total number of operations performed at this node is found by counting the number of operations performed. This total is 16 operations.

Since we chose a 4-degree node arbitrarily, the total number of operations performed to process all nodes is bounded above by 16N, where N is the number of nodes in the mesh. THIS IS AN UPPER BOUND BECAUSE 2 AND 3-DEGREE NODES WILL NEED FEWER THAN 16 OPERATIONS. Therefore, the complexity is 16N, using big-O notation, this is O(N).

4. Test Data

Data was selected to test the program. The program was tested on meshes with dimensions 10x10, 25x25, 50x50 and 100x100. A 2x3 mesh was tested but a 3x2 mesh was not tested as it is a mirror image of a 2x3 mesh. The program successfully recognized these as meshes. Further testing is ongoing.

Data was selected to test mesh-like structures. The test data was selected to fail necessary conditions. Some conditions could not be tested because an earlier test failed. Example: a node was deleted at the side. The test for number of nodes of degree 3 was never performed because the test for number of nodes of degree 2, which was performed earlier, failed the necessary conditions. All mesh-like structures were successfully detected and rejected.

Data was also selected to test the coloring technique. The test consisted of a cross-over, as depicted in Fig. 2, at a corner, on a side and in the middle. The program successfully detected the coloring violations and rejected the structure.

5. Conclusions and Future Research

This paper presented a new optimal sequential algorithm to recognize a rectangular mesh.  The algorithm has complexity O(N). The program proved that the coloring scheme, that guides its way back and forth across the rows of the mesh, works.  This technique can now be used, with minor modification, to develop algorithms for the recognition of more complex mesh-like structures, such as ring, torus, spheroid, ellipsoid, and three-dimensional mesh structures. Research is ongoing in this area to prove this assertion.

References

1. K. V. S. Ramarao,  “Distributed algorithms for network recognition problems”.  IEEE Transactions on Computers, 38(9), 1989, 1240-1248

2. A. Kazmierczak & S. Radhakrishnan,  “Optimal distributed ear decomposition with application to outerplanarity testing”.  Proc. Fifth IEEE Symposium on Parallel and Distributed Processing,  1993

3. R. Petreschim & A. Sterbini,  “Recognizing strict 2-threshold graphs in O(m) Time”.  Information Processing Letters, 54(4), 1995, 193-198.

4. T. Raschle, & K. Simon,  “Recognition of Graphs with Threshold Dimension Two”.  Proc. of the Twenty-seventh Annual ACM Symposium on the Theory of Computing,  1995, 650-661.

5. C-W. Yu & G-H. Chen, 1996.  “An Efficient Parallel Recognition Algorithm For Bipartite-Permutation Graphs”.  IEEE Transactions on Parallel and Distributed Systems, 7(1), 1996, 3-10.

6. E. Jennings, A. Lingas, L. Motyckova, “Dynamic Detection of Forests of Tree Connected Meshes”, ICCP (3), 1991, 300-301

7. R. Subbiah, S. S. Iyengar, S., Radhakrishnan, R. L. Kashyap, “An optimal distributed algorithm for recognizing mesh-connected networks”.  Theoretical Computer Science, 120(2), 1993, 261-278.

8. “The Graph Isomorphism Problem”,   http://citeseer.ist.psu.edu/fortin96graph.html

9. J. E. Hopcroft, J. K. Wong, “Linear Time Algorithm for Isomorphism of Planar Graphs”,  Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974, Pp 172-184

10. R. T. Faizullin, A. V. Prolubnikov, “Heuristic Algorithms for Solving the Graph Isomorphism Problem”  http://arxiv.math.GM/02050220v1, 21 May 2002

11. A. Kikina, R. T. Faizullin, “The Algorithm for Testing Graph Isomorphism”, VINITI, 21 Jun 1995, pp 1789-95

12. R. T. Faizullin, A. V. Prolubnikov, “A Polynomial Time Algorithm for Solution of the Graph Isomorphism Problem Which is Applicable for the Wide Class of Graphs, http://www.psy.omsu.ons.kreg.ru/session/isomorphism

13. D. C. Schmidt, L. E. Druffel, “A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Metrics”, Journal of the ACM, Vol 23, No 3, Jul 1976 Pp 433-445

14. H. Gazit, J. H. Reif, “A Randomized Parallel Algorithm for Planar Graph Isomorphism”, ACM 1990, pp 210-219

15. S. Toda, “Graph Isomorphism Problem: Its Complexity and Algorithms”,http://www.imsc.res.in/~fsttcs99/inv-abs.html, 1999

16. C. Boucher, D. Loker, “Graph Isomorphism Completeness for Subclasses of Perfect Graphs”, Ontario Combinatorics Workshop, Apr 2006

17. J. D. Wolt, T. C. Woo, R. A. Volz, “Optimal Algorithms for Symmetry Detection in Two and Three Dimensions”, http://deepblue.lib.umich.edu/bitstream/2027.42/8338/4/bam3304.0001.001.txt

18. J. Toran. “On the Hardness of Graph Isomorphism”, SIAM Journal on Computing, 2004, pp1-16

19. E. Bengoetxea, “Inexact Graph Matching Using Estimation of Distribution Algorithms”, PhD Thesis, Ecole Nationale Superieure de Telecommunications, 2002

20. A. Golubchik, “The Graph Isomorphism Problem is Polynimial”, http://arxiv.math.CO.060777v1, 29 Jul 2006

21. A. Golubchik, “The Polynomial Algorithm for Graph Isomorphism Testing”, http://arxiv.org/abs/math.CO/0202085, Feb 2002