Geometric Representation of Graphs

图的几何表示

• 批准号: RGPIN-2016-03856
• 负责人: Evans, William
• 金额: $ 1.6万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=708871
• 关键词: Geometric; Representation; Graphs

This proposal outlines a plan to explore properties of graphs that are defined geometrically. Such graphs arise, for example, in the study of transportation, communication, and sensor networks. The focus of the proposed research is on graphs defined by some notion of contact or visibility between geometric objects. Two objects are mutually visible if there exists a line segment connecting them that does not intersect another object. They are in contact if their boundaries, but not their interiors, intersect. A main theme of the proposed research concerns simultaneous representation, where one set of objects can define more than one graph. By considering contact or visibility between objects in a limited number of directions, we obtain a limited number of different contact or visibility graphs on those objects. My goal is to understand properties of these sets of simultaneously representable graphs and to design algorithms to find such representations. The most commonly studied example of simultaneous representation is the problem of finding a planar drawing of each of two graphs where each vertex is the same point in both drawings (and edges are curves that connect their endpoints). The problem is important, beyond its theoretical interest, for its application to the visual analysis of a changing network on a common set of vertices. While point/curve simultaneous representation has received a great deal of attention, the study of alternative simultaneous representations has been much more limited. I propose to study simultaneous representation using geometric objects, such as segments, rectangles, and disks, as vertices where visibility or contact determines adjacency. For example, rectangles in the plane define one graph when visibility is vertical and another when visibility is horizontal. What pairs of graphs can be represented in this fashion? Given two graphs, what is the complexity of finding such a representation if it exists? Can the existence of such a representation aid in the solving of problems restricted to these graphs? The kinds of graphs that can be represented implicitly using visibility changes depending on the type of object and on the notion of visibility. Part of this proposed research considers visibility representations that allow some amount of "X-ray vision", that is, two objects are mutually k-visible if there is a segment connecting them that intersects at most k other objects. Such graphs arise, for example, when considering networks of sensors that can penetrate a limited number of walls. The model increases the set of graphs that can be represented beyond traditional 0-visibility representations, but in a way that is limited by the geometry of the representation. An objective of the proposed research is to understand to what extent permitting k-visibility impacts the class of representable graphs and to relate this class to other well-known graph classes.

该提案概述了一个计划，以探索几何定义的图形的属性。例如，这种图出现在运输，通信和传感器网络的研究中。建议的研究重点是图形定义的几何对象之间的接触或可见性的一些概念。如果存在连接两个对象且不与另一对象相交的线段，则两个对象相互可见。如果它们的边界相交，而不是内部相交，它们就处于接触状态。所提出的研究的一个主要主题涉及同时表示，其中一组对象可以定义多个图。 通过考虑对象之间的接触或可见性在有限数量的方向上，我们得到了有限数量的不同的接触或可见性图的这些对象。我的目标是理解这些同时可表示的图的属性，并设计算法来找到这样的表示。 最常研究的同时表示的例子是找到两个图中每个图的平面图的问题，其中每个顶点是两个图中的同一点（并且边是连接它们端点的曲线）。这个问题是重要的，超越其理论的兴趣，其应用程序的可视化分析的一个共同的顶点集上的变化网络。虽然点/曲线的同时表示已经得到了很大的关注，替代的同时表示的研究已经非常有限。我建议研究同时表示使用几何对象，如段，矩形，和磁盘，作为顶点的可见性或接触确定邻接。例如，平面中的矩形在可见性为垂直时定义一个图形，而在可见性为水平时定义另一个图形。哪些图形对可以用这种方式表示？给定两个图，如果存在这样的表示，那么找到这样的表示的复杂性是多少？这种表示法的存在是否有助于解决仅限于这些图的问题？ 可以使用可见性隐式表示的图形类型取决于对象的类型和可见性的概念。这项研究的一部分考虑了允许一定量的“X射线视觉”的可见性表示，也就是说，两个对象是相互k可见的，如果有一个连接它们的线段与最多k个其他对象相交。例如，当考虑可以穿透有限数量的墙壁的传感器网络时，就会出现这样的图。 该模型增加了一组图形，可以表示超出传统的0可见性表示，但在某种程度上是由表示的几何形状的限制。拟议的研究的一个目标是了解在何种程度上允许k-可见性影响类的表示图，并将此类与其他知名的图形类。