Planar Separator Theorem - Applications - Universal Graphs

Universal Graphs

A universal graph for a family F of graphs is a graph that contains every member of F as a subgraphs. Separators can be used to show that the n-vertex planar graphs have universal graphs with n vertices and O(n3/2) edges.

The construction involves a strengthened form of the separator theorem in which the size of the three subsets of vertices in the separator does not depend on the graph structure: there exists a number c, the magnitude of which at most a constant times √n, such that the vertices of every n-vertex planar graph can be separated into subsets A, S, and B, with no edges from A to B, with |S| = c, and with |A| = |B| = (nc)/2. This may be shown by using the usual form of the separator theorem repeatedly to partition the graph until all the components of the partition can be arranged into two subsets of fewer than n/2 vertices, and then moving vertices from these subsets into the separator as necessary until it has the given size.

Once a separator theorem of this type is shown, it can be used to produce a separator hierarchy for n-vertex planar graphs that again does not depend on the graph structure: the tree-decomposition formed from this hierarchy has width O(√n) and can be used for any planar graph. The set of all pairs of vertices in this tree-decomposition that both belong to a common node of the tree-decomposition forms a trivially perfect graph with O(n3/2) vertices that contains every n-vertex planar graph as a subgraph. A similar construction shows that bounded-degree planar graphs have universal graphs with O(n log n) edges, where the constant hidden in the O notation depends on the degree bound. Any universal graph for planar graphs (or even for trees of unbounded degree) must have Ω(n log n) edges, but it remains unknown whether this lower bound or the O(n3/2) upper bound is tight for universal graphs for arbitrary planar graphs.

Read more about this topic:  Planar Separator Theorem, Applications

Famous quotes containing the word universal:

    The basis of world peace is the teaching which runs through almost all the great religions of the world. “Love thy neighbor as thyself.” Christ, some of the other great Jewish teachers, Buddha, all preached it. Their followers forgot it. What is the trouble between capital and labor, what is the trouble in many of our communities, but rather a universal forgetting that this teaching is one of our first obligations.
    Eleanor Roosevelt (1884–1962)