ABSTRACT SPHERE-OF-INFLUENCE GRAPHS

The SIG, or ''sphere-of-influence graph,'' G(S) of a set S of points i n the plane was introduced by G. Toussaint. To each point of S assign an open ball centered at that point of radius equal to the smallest di stance from that point to any other point of S. Then the vertex set of G(S) is S and two vertices x and y are adjacent whenever their open b alls intersect. An abstract SIG is isomorphic to some G(S). It is veri fied that every path and every cycle is a SIG, and that every tree is an induced subgraph of some SIG. Corresponding but different results f or the proximity graphs which use closed balls are derived. Several un solved problems are explicitly stated.