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.