What is ISGCI?

ISGCI is an encyclopaedia of graphclasses with an accompanying java application that helps you to research what's known about particular graph classes. You can:
  • check the relation between graph classes and get a witness for the result
  • draw clear inclusion diagrams
  • colour these diagrams according to the complexity of selected problems
  • find the P/NP boundary for a problem
  • save your diagrams as Postscript, GraphML or SVG files
  • find references on classes, inclusions and algorithms

Database contents

1509 classes
178357 inclusions
updated 2014-09-09


Latest news

  • 2014-03-15 Add preview tooltips for references.
  • 2013-12-19 Bug fixed that prevented the application from running.
  • 2013-09-16 Added adjoints as the first directed graph class.