Superpatterns and Universal Point SetsBannister, Michael J. and Cheng, Zhanpeng and Devanny, William E. and Eppstein, David (2013) Superpatterns and Universal Point Sets. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 208219(Official URL: http://dx.doi.org/10.1007/9783319038414_19). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_19
AbstractAn 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.
Actions (login required)
