Superpatterns and Universal Point Sets

Abstract

An old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all n-vertex planar graphs. We connect this problem to the theory of permutation patterns, where another open problem concerns the size of superpatterns, permutations that contain all patterns of a given size. We generalize superpatterns to classes of permutations determined by forbidden patterns, and we construct superpatterns of size n^2/4 + Theta(n) for the 213-avoiding permutations, half the size of known superpatterns for unconstrained permutations. We use our superpatterns to construct universal point sets of size n^2/4 - Theta(n), smaller than the previous bound by a 9/16 factor. We prove that every proper subclass of the 213-avoiding permutations has superpatterns of size O(n log^O(1) n), which we use to prove that the planar graphs of bounded pathwidth have near-linear universal point sets.

GD 2013 special issue of JGAA

References in corpus (3)

• Combinatorics and geometry of finite and infinite squaregraphs
• Universal point sets for planar three-tree
• Drawing Permutations with Few Corners

Cited by in corpus (8)

• Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity
• Universal point sets for planar three-tree
• Containing all permutations
• An exponential bound for simultaneous embeddings of planar graphs
• Every Collinear Set in a Planar Graph Is Free
• An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs
• Embedding Four-directional Paths on Convex Point Sets
• A Universal Point Set for 2-Outerplanar Graphs