Algorithmic Aspects of Intersection Graph Models

图上算法的设计和分析是计算机科学的一个主要分支学科。图（由顶点和边组成）不仅在计算机科学和数学中无处不在，而且在整个科学和工程领域都无处不在。图的广泛应用产生了一系列不同的特性。这一基本事实激发了对结构化图类的广泛研究，即具有某些共同结构性质的图族。例如，当图形用于模拟芯片上的网络时，这些图形必须是平面的，因为它们需要在平面上布局，以便它们的任何边都不会交叉。然而，无论我们使用哪种标准数据结构来表示图，大多数重要的结构属性都足够复杂，可以“很好地隐藏”在这些基本表示中。幸运的是，对于许多模拟实际应用程序的图，存在更复杂的表示。特别地，如果我们能双射地将集合族的一个集合赋给图的一个顶点，使得图中顶点对之间的邻接关系双射地对应于相应集合对的非空交点，则图被称为集合族的交集图。这样的集合族称为图的交集模型。事实证明，许多重要的图类可以被描述为由某种几何构型衍生的集合族的相交图。这类图中最突出的例子可能是区间图，即实线上区间的相交图。几何物体相交图的应用横跨几个实际领域，如生物学和生物信息学（如DNA的物理作图和基因组重建）、移动计算和传感器网络、地图标记等。特定的交集模型提供了对一类图的固有结构的自然和直观的理解，并且在为硬优化问题提供有效的算法以及证明硬度结果方面非常有帮助。因此，建立这样的交集模型来表征某些图族是非常重要的。在提出的研究中，我们计划探索各种相交模型，通过这些模型可以表示许多重要的图族，并更深入地了解它们的潜在组合结构。此外，我们计划为重要的图类设计新的交集模型，目前还没有已知的交集模型。揭示图的交集模型的固有属性将从本质上帮助我们理解有效计算的边界，无论是在传统意义上（多项式与NP-hard）还是在参数化复杂性的意义上。

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.