Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Twentyfirst International Symposium on Graph Drawing, GD 2013
DOI: 10.7155/jgaa.00318
Superpatterns and Universal Point Sets
Vol. 18, no. 2, pp. 177209, 2014. Regular paper.
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 straightline drawings of all nvertex 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+Θ(n) for the 213avoiding permutations, half the size of known superpatterns for unconstrained permutations. We use our superpatterns to construct universal point sets of size n^{2}/4−Θ(n), smaller than the previous bound by a 9/16 factor. We prove that every proper subclass of the 213avoiding permutations has superpatterns of size O(nlog^{O(1)}n), which we use to prove that the planar graphs of bounded pathwidth have nearlinear universal point sets.

Submitted: December 2013.
Reviewed: February 2014.
Revised: March 2014.
Accepted: March 2014.
Final: April 2014.
Published: May 2014.
