About the 2001 Topic

Research Program

Education Program

General Information

About DIMACS

DCI Home

DCI '01 Home

AT&T Foundation

AT&T Learning Network

  Research Program **



Week 1 Topic
Intersection Graphs, Tolerance Graphs
July 9 - 13, 2001


Program Chairs:

Fred McMorris, Illinois Institute of Technology, mcmorris@iit.edu

Announcement

Schedule

Speakers & Participants

Abstracts

All week one lectures will be given in the first floor auditorium.


Given a family of sets, associate a vertex to each set and declare two vertices adjacent if and only their corresponding sets have a non-empty intersection. The resulting graph is called an intersection graph. When restrictions are placed on the sets, many intriguing results can be obtained which often have significant applications. For example, when the sets are intervals the resulting intersection graph is called an interval graph and has found applications in molecular biology. When the sets are certain convex sets in the plane determined by points and their proximity to each other, resulting intersection graphs have proven useful in pattern recognition and data analysis. When the sets are subtrees of a tree, the resulting intersection graph is called a chordal graph and has been an important tool in evolutionary history estimation; etc. When conditions are also placed on the "amount" of intersection of the sets, one obtains tolerance intersection graphs. These graphs too have interesting mathematical properties as well as applications to problems of society.

Page last updated: June 22, 2001.