Geometric Embedding of Graphs and Random Graphs

Abstract

In a spatial graph model, vertices are embedded in a metric space, and the link probability between two vertices depends on this embedding in such a way that vertices that are closer together in the metric space are more likely to be linked. In this thesis we study spatial embedding of graphs and random graphs when the metric space is (R^n,|| . ||_∞).

The first part of this thesis is devoted to the study of (R^2,|| . ||_∞)-geometric graphs, graphs whose vertices are points in R^2 and two vertices are adjacent if and only if their distance is at most 1. Such graphs are called square geometric graphs. We present a polynomial-time algorithm for recognition of a subclass of square geometric graphs. Moreover if the input graph is a square geometric graph then the algorithm returns the orderings of the x and y coordinates that determine the embedding.

The second part of this thesis is devoted to the study of spatial embedding of random graphs when the metric space is (R ,|| . ||_∞). Let w: [0,1]^2 ⟶ [0,1] be a symmetric function, and consider the random process G(n,w), where n vertices are chosen from [0,1] uniformly at random, and w governs the edge formation probability. Such a random graph is said to have a linear embedding, if the probability of linking to a particular vertex v decreases with distance. The rate of decrease, in general, depends on the particular vertex v. A linear embedding is called uniform if the probability of a link between two vertices depends only on the distance between them. In this thesis we give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs where w attains only a finite number of values.