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, Bordeaux, France , 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
ID Code:1376

Repository Staff Only: item control page

References

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990); Originally presented at STOC 1988

Chrobak, M., Payne, T.: A linear-time algorithm for drawing a planar graph on a grid. Inform. Proc. Lett. 54(4), 241–246 (1995)

Schnyder, W.: Embedding planar graphs on the grid. In: Proc. 1st ACM–SIAM Symp. on Discrete Algorithms, pp. 138–148 (1990)

Brandenburg, F.J.: Drawing planar graphs on 89n2 area. In: Proc. Int. Conf. Topological and Geometric Graph Theory. Electronic Notes in Discrete Mathematics, vol. 31, pp. 37–40. Elsevier (2008)

Dolev, D., Leighton, T., Trickey, H.: Planar embedding of planar graphs. Advances in Computing Research 2, 147–161 (1984)

Kurowski, M.: A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inform. Proc. Lett. 92(2), 95–98 (2004)

Mondal, D.: Embedding a Planar Graph on a Given Point Set. Master’s thesis, Dept. of Computer Science, U. of Manitoba (2012)

Demaine, E., O’Rourke, J.: Smallest Universal Set of Points for Planar Graphs (Problem 45). In: Demaine, E., Mitchell, J.S.B., O’Rourke, J. (eds.) The Open Problems Project (2002-2012)

Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified positions. Amer. Math. Monthly 98(2), 165–166 (1991)

Angelini, P., Di Battista, G., Kaufmann, M., Mchedlidze, T., Roselli, V., Squarcella, C.: Small point sets for simply-nested planar graphs. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 75–85. Springer, Heidelberg (2011)

Fulek, R., Tóth, C.D.: Universal point sets for planar three-trees. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, pp. 341–352. Springer, Heidelberg (2013)

Eppstein, D.: Drawing arrangement graphs in small grids, or how to play Planarity. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 436–447. Springer, Heidelberg (2013)

Bereg, S., Holroyd, A.E., Nachmanson, L., Pupyrev, S.: Drawing permutations with few corners. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 484–495. Springer, Heidelberg (2013)

Arratia, R.: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Elect. J. Comb. 6, N1 (1999)

Eriksson, H., Eriksson, K., Linusson, S., Wästlund, J.: Dense packing of patterns in a permutation. Ann. Comb. 11(3-4), 459–470 (2007)

Miller, A.: Asymptotic bounds for permutations containing many different patterns. J. Comb. Theory A 116(1), 92–108 (2009)

Marcus, A., Tardos, G.: Excluded permutation matrices and the Stanley–Wilf conjecture. J. Comb. Theory A 107(1), 153–160 (2004)

Rotem, D.: Stack sortable permutations. Discrete Math. 33(2), 185–196 (1981)

Knuth, D.: Vol. 1: Fundamental Algorithms. In: The Art of Computer Programming. Addison-Wesley, Reading (1968)

Dietz, P.F.: Maintaining order in a linked list. In: Proc. 15th ACM Symp. on Theory of Computing, pp. 122–127 (1982)

Bukh, B., Matoušek, J., Nivasch, G.: Lower bounds for weak epsilon-nets and stair-convexity. Israel J. Math. 182, 199–208 (2011)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: 4.7 Dominance drawings. In: Graph Drawing: Algorithms for the Visualization of Graphs, pp. 112–127. Prentice-Hall (1999)

Eppstein, D., Simons, J.A.: Confluent Hasse diagrams. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 2–13. Springer, Heidelberg (2011)

Bannister, M.J., Devanny, W.E., Eppstein, D.: Small superpatterns for dominance drawing (manuscript 2013)