Superpatterns and Universal Point Sets

Bannister, 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 23-25, 2013 , pp. 208-219(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_19).

Full text not available from this repository.

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 + Θ(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 − Θ(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(nlog O(1) n), which we use to prove that the planar graphs of bounded pathwidth have near-linear universal point sets.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 13 Aug 2014 16:07
Last Modified: 13 Aug 2014 16:07
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1376

Actions (login required)

View Item View Item