Many computationally hard discrete optimization problems on graphs become easy (polynomially sovable) when restricted to special classes of graphs. Obviously, it is the structure of those graphs that makes them "easy". Very often, such a structure is exhibited by a "parse tree" of graphs in the class. This suggests an algebra underlying the process whereby graphs of the class can be constructed. As an example, cographs (complement reducible graphs) can be considered values of terms in an algebra consisting of the operations of graph union (binary), complement (unary), and trivial (nullary).
The focus of my research has been algorithms on graphs embeddable in k-trees, graphs constructed from (k+1)-complete primitives by "glueing" them on k-complete subgraphs, in a tree-like manner. For a fixed value of parameter k, these partial k-trees are exactly the graphs of bounded treewidth of Robertson and Seymour, the concept developed independently in about the same time. The titles of papers should give some idea of the problems in this area, and their contents provide some solutions to those (see also a more up-to-date publication list).
(Back to Home page)