Contents

Main window

File menu

New window

Open a new, independent ISGCI window.

Export to Postscript

Export the current drawing as a Encapsulated Postscript (EPS) file, which can be included in your papers. Papersize, scaling and colour or black-and-white print can be selected. A dialogue box will be popped up where you can select the file to export to. You need at least Java 1.3 for printing to work.

Exit

Close all windows and exit ISGCI.

View menu

Naming preference

Select the prefered name for classes in inclusion diagrams. A class can be defined in different ways and accordingly have different names. This menu item will popup a dialogue box that allows you to select the prefered name for classes that have more than one name. The options are:

• Basic. Any name that does not qualify as one of the other preferences.
• Forbidden subgraphs. Characterization by forbidden subgraphs.
• Derived. Characterization by set operations (intersect, union, complement) on (an)other graph class(es).

Graph classes menu

Browse database

Browse the database by class name. The top half of the dialogue box display a list of classes. The Filter box can be used to limit the display of classes. Classes are sorted alphabetically, where capitals come before lower case, and special characters are ignored for the sorting order. Clicking on a class will select it and display information in the lower half of the window.
The information displayed is the complexity on the current graph class for one problem, and, below that, super-, sub- and equivalent classes.
=> Single clicking a class in one of the three lower lists selects it and double clicking will display information on it in the current window.
=> Clicking Class info will display information on the current graphclass, including the complexity of all problems.
=> Clicking Inclusion info will display the inclusion between the current graph class and the selected one from one of the super/sub/equivalent lists.

Find relation

Select a graph class in the top list, and one in the bottom list and press Find relation to find the relation between them. The Filter boxes can be used to limit the display of classes in both lists. If one of the classes is a subclass of the other an inclusion path will be displayed. Otherwise the minimal common superclasses and maximal common subclasses are displayed.
=> Clicking on an inclusion button in the result window will display references to this inclusion.

Draw

Select one or more graph classes, whether you would like their super/subclasses to be drawn also, and click New drawing to create a new inclusion diagram in the current window. The Filter box can be used to limit the display of classes.

Problems menu

Boundary/open classes

Selecting a problem from the submenu to this item will display a dialogue box with three lists of graph classes:
Minimal NP-complete classes have a direct subclass for which the problem is not NP-complete,
open classes for which the complexity is unknown and
maximal P classes have a direct superclass for which the problem is not known to be in P.
=> Clicking on a class will select it.
=> Clicking Draw will display the border between P and NP-complete surrounding the selected graph class.
=> Clicking Class info will display information on the selected graph class.

Colour for problem

Selecting a problem from the submenu to this item will colour inclusion diagrams according to the complexity of the selected problem, see problem definitions

Problem definitions

• Red for NP-complete classes.
• White for open classes.
• Dark green for classes in P.
• Light green for classes on which the problem can be solved in linear time.

Recognition

The recognition problem for a graphclass X has as input a graph G and asks whether G is in X.

Independent set

An independent set of a graph is a pairwise independent subset of its vertices. The independent set problem has as input a graph G and a natural number k and asks whether G has an independent set of at least k vertices.

Weighted independent set

The weighted independent set problem has as input a vertex weighted graph G and a real number k and asks whether G has an independent set with total weight at least k.

Domination

A dominating set of a graph G is a subset of its vertices such that every vertex of the graph is either in the set itself or has a neighbour in the set. The domination (or dominating set) problem has as input a graph G and a natural number k and asks whether G has a dominating set of size at most k.

Cliquewidth

The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

• creation of a vertex with label i,
• disjoint union,
• renaming labels i to label j,
• connecting all vertices with label i to all vertices with label j.

The colouring happens in the following way:

• Red for classes whose cliquewidth is not constant bounded.
• White for open classes.
• Light green for classes with constant bounded cliquewidth.

Cliquewidth expression

The cliquewidth expression problem has as input a graph G and as output an expression constructing that graph that uses only a constant number of labels. The colouring happens in the following way:

• Red for classes whose cliquewidth is not constant bounded, or for which finding a clique expression is NP-complete.
• White for open classes.
• Dark green for classes that have constant bounded cliquewidth, and a clique expression can be found in polynomial time.
• Light green for classes with constant bounded cliquewidth and for which a clique expression can be found in linear time.

Filtering lists of graph classes

Filtering is case insensitive and the filtering process has some limited knowledge about graph names. E.g. if you filter on 'chair', 'fork' will also be found.

Back to contents