Algorithmic Aspects of Intersection Graph Models

The design and analysis of algorithms on graphs is a major sub-discipline 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 networks-on-chips, 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 non-empty 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. NP-hard) and in the sense of parameterized complexity.

We consider the community of Mobile Computing and Wireless Networks as potential beneficiaries of our research. It is very common for wireless networks to be modeled by geometric intersection graphs, since the placement of the devices (e.g. sensors/transmitters/receivers) and the interaction between them is inherently influenced by geometric and spatial constraints and characteristics, such as the distance between them (too long distance implies non-communication, while too short distance may imply interference between the transmitted signals) and the various physical obstacles that affect communication (e.g. mountains or buildings). Although several models have been considered (e.g. acknowledge-communication graphs and interference graphs), a model that has been prevalently used both in static wireless networks and in mobile ad hoc networks is that of unit disk graphs, where each wireless device is represented by a point on the plane and an edge is drawn if the distance between two points is at most some fixed constant. The main challenge in developing protocols for wireless and sensor networks is to define appropriate abstract models that describe well their behavior: these models have to be simple enough (in order to analyze them and to design algorithms with provably good performance) but not too simplistic (in order to be realistic). The introduction of new geometric intersection models that can capture more realistically inherent properties and practical restrictions of wireless networks, as well as the development of efficient algorithms, may result in essentially improved and more efficient wireless network protocols. Implementing such improved protocols in real wireless networks has the potential to drive economic growth and impact several application domains in the UK such as mobile communication, transportation and military.

Further end-beneficiaries of our research include the community of Computer Graphics and Visualization, which deals with the representation and visualization of complex information and large structured data sets. The problem of information visualization is often approached as the problem of visualizing and navigating through a graph. Data that impose a hierarchical structure may be represented by simple graphs such as trees and related graph structures, e.g. business organizational charts, phylogenetic trees and molecular maps, while other applications involve representations of information by more general and complex graphs, e.g. virtual reality (scene graphs) and Computer-Aided-Design (CAD). The ability of efficiently visualizing and navigating in these potentially large graphs is often a crucial part of applications; prominent examples include satellite navigation and diagnostic medical imaging. The theoretical study of intersection graph models in 2D and 3D, and in particular the design of efficient algorithms on these models, may underpin the development of innovative software libraries and frameworks for practical applications, thus providing a considerable potential for the economy and the society due to the wide use of such applications from the industry and the public. However the advances in Computer Graphics (CG) are mostly delivered by practitioners and software developers, who may have difficulties in transforming the theoretical knowledge into applications. Thus, within our pathway towards achieving practical impact in CG, we consider the community of Graph Drawing (GD) as the immediate beneficiaries of our research, since the research area of GD straddles between theory and practice. The development of final products for practical applications in CG would certainly require a separate serious effort with deep knowledge of CG techniques.

Finally, we see our research as promoting and strengthening the area of algorithms and complexity within the UK, thus helping the presence of high quality theoreticians whose research skills will be of interest to the high-tech industry.