clique-width

Graphs are used as models in various applications ranging from supplynetworks to interaction between human beings. These applicationsrequire algorithms processing graphs. Usually the input of analgorithm is given as a list of vertices (branching points of thenetwork, persons, or objects) and a list of edges (connections orrelations between vertices). Lots of practically important ortheoretically interesting problems on graphs are intractable if thegraph is given this way, but become tractable if instead aconstruction manual is provided. Such a manual describes basicbuilding blocks and simple operations to combine components.The parameter clique-width measures the complexity of such aconstruction manual in the following way. Our basic block is a graphconsisting of one vertex and no edges. The vertex has a colour. Theoperations are disjoint union (set one graph aside another one withoutcreating any new edges), recolouring of vertices (for example: allblue vertices become green), and inserting edges (for example: connecteach red vertex to each yellow one). The complexity is the number ofdifferent colours used. A construction plan involving k colours iscalled k-expression. For each graph G, the minimum k such that ak-expression for G exists is called cwd(G).Finding a cwd(G)-expression for a given graph G is itself analgorithmic problem. Unfortunately very little is known about it:* We know the graphs that are constructible using only one colour. These are the graphs without edges.* Two colours suffice if and only if the graph does not contain a path on 4 vertices.* There is an efficient algorithm deciding whether one can construct a graph using at most 3 colours.This project will extend this knowledge. We consider graphs in specialclasses. These classes are restricted to enforce an easy structure ofthe graphs within, but are rich enough to allow graphs of arbitraryclique-width. Our goal is an efficient algorithm computing acwd(G)-expression for each graph G in the special class.It is not known whether such an algorithm exists. In case we cannotdesign an efficient algorithm we will provide some evidence that thedesired algorithm does not exist.