Geometric Representation of 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.