This is a (perhaps re-) implementation of an algorithm discovered by Arnborg, Courcelle, Proskurowski, and Seese. They discovered that, using rewrite rules, you can determine, in linear time, whether a particular graph of bounded treewidth has a property that is describable in monadic second order logic. (Whew. That's a mouthful.) Unfortunately, the proof was non-constructive, which means tht you are on your own if you want to automagically generate an algorithm that checks whether or not a set of graphs has a particular property or not.

This is the second attempt at the algorithm. As of 9/5/3 it works as well! It runs in O(n) time! The next step is to write up something about how it all went.

To use it, coerce your graph into the form implied by the .graph files in this directory. Then, choose from among the properties you want to test, and call the program like so:

membership.py planar3tree < input.graph | neato -Tps > output.ps
You can interchange any set of reduction graphs for planar3tree, including both tree and partial3tree or a set you make up yourself. 

Icon  Name                    Last modified      Size  Description
[DIR] Parent Directory                             -   
[   ] 3tree.graph             16-Jul-2003 10:52  162   
[   ] 3treePartial.ps         16-Jul-2003 10:52   10K  
[   ] 3treePlanar.ps          16-Jul-2003 10:52   13K  
[   ] buggy.graph             22-Sep-2003 16:37   41   
[TXT] combo.py                04-Sep-2003 14:38  1.8K  
[   ] combo.pyc               04-Sep-2003 20:14  2.8K  
[TXT] graphs.py               10-Sep-2003 22:15  5.0K  
[   ] graphs.pyc              10-Sep-2003 22:15  7.2K  
[TXT] membership.py           03-Oct-2003 15:38  1.8K  
[TXT] outerplanar.py          26-Oct-2003 12:38  1.5K  
[   ] outerplanar.pyc         03-Oct-2003 15:26  2.4K  
[TXT] partial3tree.py         18-Sep-2003 00:21  1.3K  
[   ] partial3tree.pyc        18-Sep-2003 00:20  2.1K  
[TXT] planar3Tree.py          18-Sep-2003 00:21  1.7K  
[   ] planar3Tree.pyc         16-Jul-2003 10:52  2.7K  
[TXT] reduction.py            26-Oct-2003 12:36  9.1K  
[   ] reduction.pyc           10-Sep-2003 22:12   12K  
[   ] t.ps                    05-Sep-2003 14:49   10K  
[   ] test                    27-Aug-2003 14:51   38   
[   ] tinytree.graph          16-Jul-2003 10:52   51   
[   ] tinytree.ps             05-Sep-2003 13:41  8.2K  
[TXT] tree.py                 05-Sep-2003 11:39  355   
[   ] tree.pyc                05-Sep-2003 11:39  624
Apache/2.2.3 (Debian) mod_python/3.2.10 Python/2.4.4 PHP/4.4.4-8+etch6 mod_perl/2.0.2 Perl/v5.8.8 Server at soy.dyndns.org Port 80