About ISGCI

Background

Over the years, the mathematics and computer science communities have described many special graph classes in an attempt to enlarge both our understanding of fundamental properties of graphs, and our ability to solve practical problems efficiently. This work has been - and still is - so fruitful that a large number of classes have been defined, whose relations are difficult to overview even for the initiated. In an attempt to make this field more accessible the book Graph Classes - A Survey by A. Brandstaedt, V.B. Le, J. Spinrad documents over 300 classes. ISGCI goes one step further, by allowing the user to examine the relation between graph classes interactively. ISGCI provides the user with

  • drawings of classes and their relations
  • references on classes and their relations
  • colouring of class diagrams according to the computational complexity of selected problems
  • references to algorithms or complexity proofs for selected problems

How to cite ISGCI

When you wish to cite ISGCI, you can use the following data:

Author H.N. de Ridder et al.
Title Information System on Graph Classes and their Inclusions (ISGCI)
URL http://www.graphclasses.org
Date Can be found on the left below the menu.

Here is a bibtex entry for ISGCI:

@misc{isgci,
author="de Ridder, H. N. and others",
title="{{I}}nformation~{S}ystem~on~{G}raph~{C}lasses~and~their~{I}nclusions~({I}{S}{G}{C}{I})",
howpublished="\url{http://www.graphclasses.org}",
}

History

Version 1

Version 1.0 was created in 1999 at Rostock University, Department of Computer Science, by F. Siegemund under supervision of T. Szymczak after an idea by A. Brandstaedt and V.B. Le. It consisted solely of a Java 1.0 applet and contained classes and inclusions, but no information on problems and hence no colouring. The only information available on classes were their names, in Latex, not formatted. Despite its simplicity, it was an excellent basis to determine the use of such a system as well the limitations of the implementation. The two foremost limitations perceived were maintainability and the fact that inclusions that were obvious from the definition of a graphclass were often not in the system. Version 2 was created to cure these limitations.

Version 2

Version 2 was released in 2001 and was created by S. Knorr, M. Rzehak, and H.N. de Ridder with the last one supervising. The web pages were designed by K. Erdmann. H.N. de Ridder has been responsible for ISGCI ever since. Version 2 was written in Java 1.1 and consisted of a complete rewrite of the applet and a new application to deduce inclusions automatically. From now on, e.g. P4-free would not just be a name, but define a graphclass by forbidding the subgraph P4.

During the years 2001-2008 many improvements were made to version 2. The deduction algorithms were extended and improved (D. Bayer, N. Ryabova, H.N. de Ridder), the data storage was changed to XML (N. Ryabova, H.N. de Ridder), references were linked to ZMATH entries (D. Bayer, U. Nagel, T. Teige), problems were added (H.N. de Ridder), drawings of smallgraphs were added (M. Mowitz, H.N. de Ridder and others), web pages for classes with definitions etc. were added (H.N. de Ridder), searching in the web pages and in the applet was implemented (D. Bayer, H.N. de Ridder). Finally many other improvements were made to the system and an enormous amount of data was added (H.N. de Ridder).

However, technology was changing and the applet became unusable in modern Java systems, because the applet was still written using the AWT graphics toolkit and Java had switched to Swing. This was cured by version 3.

Version 3

Version 3 was released in 2010 and was created by H.N. de Ridder. It replaced the AWT visualization code by Swing, switched from applet to jnlp application and improved the layout of the web pages using the capabilities of modern browsers. In the summer of 2012, Nathann Cohen added an interface to the ISGCI database in the Sage mathematics system. Version 3 is the current release.

Version 4

Version 4 is under development. Features are published in version 3 until version 4 is complete and replaces version 3.

The first of these features is support for graph parameters. The requirements were formulated in cooperation with M. Vatshelle and M. Sorge and the implementation was done by F. Abt, S. Brütsch, J. Krajenski, J. Messmer, D. Söll and M. Strecke at Konstanz University. The initial data consisting of 30 parameters and their relations was supplied by M. Sorge, based on compilations by R. Sasak and F. Spiess.

Some statistics

Since version 1.0 in 1999, ISGCI has become faster, more stable, more capable and better informed. In June 2003, the database contained over 600 classes and more than 36,000 inclusions. In March 2010, the number of classes has grown to more than 1000 and the number of inclusions to more than 100,000. Interestingly, the number of inclusions remained at about 10% of the square of the number of classes throughout the history of ISGCI.

In August 2010, the database contained 1109 classes and 114,524 inclusions. To obtain these, the system investigated/deduced 4252 classes and 3,253,127 inclusions. Of these, 3,236,623 or 99.5% were proper inclusions, 13,052 or 0.4% were equalities and for 3452 or 0.1% the system could not determine whether the inclusion is proper or in fact an equality.

The database contained 1394 references, 1108 or 80% of which had a ZMATH link. 100% of the algorithms in the system and 92% of the inclusions had a reference. The remaining inclusions were deduced automatically in multiple steps over graph classes that were generated automatically and deleted afterwards.

Future

We will continue to improve the software and to extend the database by new classes, inclusions and algorithms. We appreciate it very much if you would contact us if you find an error or omission in the software or the database, if you have an idea for a new feature, or if you have described a new graph class or algorithm.

Acknowledgements

Many users have contributed corrections, omissions or ideas to ISGCI. We thank all of them, especially

  • N. Cohen (created the Sage interface)
  • P. Irzhavski (contributed data for the Hamiltonian problems)
  • P. Ochem (corrected many omissions)
  • A. Salamon (provided ideas)
  • M. Sorge (specifications and review of graph parameters)
  • M. Vatshelle (specifications of graph parameters)

and further

  • P. Drange
  • L. Feuilloley
  • G. Guninksi
  • lkozma
  • oscarlin
  • M.D. Safe
  • F. Soulignac

and

  • N. Aerts
  • A. Agrawal
  • L. Alcon
  • B. Alexeev
  • F. Bonomo
  • T. Bootby
  • G. Borradaile
  • T. Calamoneri
  • Y. Cao
  • S. Chaplick
  • AbnerCYH
  • K. Dabrowski
  • M. De Biasi
  • J. Diaz
  • diego1609
  • P. Dorbec
  • ef
  • L. Erickson
  • A. Farrugia
  • E. Feicho
  • E. Fox-Epstein
  • M. Francis
  • D. Gernert
  • gilamor
  • M. Gille
  • M.C. Golumbic
  • F. Gurski
  • hardmath
  • P. Jonsson
  • jsoto
  • M. Kasprzak
  • J. King
  • T. Kloks
  • C. Komusiewicz
  • M. Kuhlmann
  • A. Labarre
  • M. Lafond
  • A. Leitert
  • lericks4
  • T. Liu
  • G. Mertzios
  • M. Milanic
  • G. Morel
  • T. Mueller
  • J. Nastos
  • M. Nich
  • S. Nikolopoulos
  • R. Oliveira Lopes
  • S.-i. Oum
  • L. Palios
  • F. Pereira
  • D. Pritchard
  • Protosdrone
  • V. Santos
  • O. Schaudt
  • S. Sether
  • A. Takaoka
  • A. Uzzell
  • M. Vatshelle
  • R. Wehr
  • K.D. Witzel
  • yixin
  • T. Zaslavsky

Please contact us if you contributed and your name is missing from this list.

ISGCI uses the JGraphT library, which is distributed under the LGPL v2.1 and is available at the JGraphT website, or by emailing us. The website uses the Rosario font by Omnibus-Type.

Database contents

1600classes
217586inclusions
26190complexities
46905bounds

updated 2016-07-07


Latest news

  • 2015-03-26 Added support for graph parameters.
  • 2014-03-15 Add preview tooltips for references.
  • 2013-12-19 Bug fixed that prevented the application from running.