EPSRC Reference: 
EP/K022660/1 
Title: 
Algorithmic Aspects of Intersection Graph Models 
Principal Investigator: 
Mertzios, Dr G 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Engineering and Computing Sciences 
Organisation: 
Durham, University of 
Scheme: 
First Grant  Revised 2009 
Starts: 
09 October 2013 
Ends: 
30 November 2015 
Value (£): 
96,802

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
21 Nov 2012

EPSRC ICT Responsive Mode  Nov 2012

Announced


Summary on Grant Application Form 
The design and analysis of algorithms on graphs is a major subdiscipline of Computer Science. Graphs (composed of vertices and edges) are ubiquitous not only in Computer Science and Mathematics but across the whole spectrum of Science and Engineering. The vast range of applications of graphs result in a whole host of different properties of interest. This basic fact has motivated the extensive study of structured graph classes, i.e. of families of graphs that all share some common structural property. For example, when graphs are used to model networksonchips, it is necessary that such graphs are planar for they need to be laid out on the plane so that none of their edges cross. However, no matter which standard data structures we use to represent graphs, most important structural properties are complex enough to be "well hidden" within these basic representations. Fortunately, more sophisticated representations exist for many graphs that model practical applications. In particular, a graph is called an intersection graph of a family of sets, if we can bijectively assign a set of this family to a vertex of the graph, such that adjacencies between pairs of vertices in the graph correspond bijectively to nonempty intersections of the corresponding pairs of sets. Such a family of sets is then called the intersection model of the graph.
It turns out that many important graph classes can be described as intersection graphs of set families that are derived from some kind of geometric configuration. Probably the most prominent example of this kind is that of interval graphs, i.e. the intersection graphs of intervals on the real line. The applications of intersection graphs of geometric objects straddle several practical fields, such as biology and bioinformatics (e.g. the physical mapping of DNA and the genome reconstruction), mobile computing and sensor networks, map labeling, etc. Specific intersection models provide a natural and intuitive understanding of the inherent structure of a class of graphs, and turn out to be extremely helpful in delivering efficient algorithms for hard optimization problems, as well as in proving hardness results. Consequently, it is of great importance to establish such intersection models that characterize certain families of graphs. Within the proposed research we plan to explore the various intersection models by which many important families of graphs can be represented, as well as to more deeply understand their underlying combinatorial structure. Moreover, we plan to devise new intersection models for important graph classes, for which no intersection model is known so far. Revealing the inherent properties of intersection models for graphs will essentially help us in understanding the boundaries of efficient computation, in both the traditional sense (polynomial vs. NPhard) and in the sense of parameterized complexity.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
