SCS

Abstract

I will give an overview of ongoing research concerning networks in two-dimensional space, emphasizing two aspects. (1) There is a general class of "proximity graphs", defined for arbitrary vertices, which are always connected. Applying to random points gives a class of random networks which are connected and have bounded mean degree. This class has scarcely been studied, but seems an appealing modeling alternative to the classical geometric random graphs for which one cannot have both connectivity and bounded mean degree. (2) The models above envisage e.g. inter-city road networks linking distinct cities. To instead abstract online maps, suppose that for each pair of points in the plane (addresses) there is a route between them. Does it make sense to think of such a network as a realization from a probability distribution invariant under Euclidean translation and scaling?