On Small Universal Data Structures and Related Combinatorial Problems.
Richard A. DeMillo, Stanley C. Eisenstat, Richard J. Lipton · 1978
A universal graph for a class of graphs T is a graph G such that every graph in T can be embedded in G with worst-case (average case) loss of proximity bounded by a fixed constant. A universal graph can be interpreted as a universal data structure. Upper and lower bounds are derived for a variety of restrictions on T and G. (Author)