On graphs which contain all sparse graphs

This chapter presents a study on graphs which contain all sparse graphs. Let ℋ_n denote the class of all graphs with n edges and denote by s(n) the minimum number of edges a graph G can have, which contains all H ∊ ℋ_n as subgraphs. The chapter discusses the problem of determining the minimum number of edges, denoted by s'(n) a graph can have, which contains every planar graph on n edges as a subgraph. The chapter discusses a lower bound for s(n) and while discussing an upper bound for s(n), it is proved (by the probability method) that there exists a graph with cn² log log n/log n edges that contains all graphs with at most n edges. The chapter presents a theorem to give an upper bound of n^3/2 for the universal graphs that contain all planar graphs on n edges.