Small superpatterns for dominance drawing

DOI10.1137/1.9781611973204.9MaRDI QIDQ5194761zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, William E. Devanny, David Eppstein

Publication date 17 September 2019

Published in 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.3770

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We exploit the connection between dominance drawings of directed acyclic graphs and permutations, in both directions, to provide improved bounds on the size of universal point sets for certain types of dominance drawing and on superpatterns for certain natural classes of permutations. In particular we show that there exist universal point sets for dominance drawings of the Hasse diagrams of width-two partial orders of size O(n^{3/2}), universal point sets for dominance drawings of st-outerplanar graphs of size O(nlog n), and universal point sets for dominance drawings of directed trees of size O(n^2). We show that 321-avoiding permutations have superpatterns of size O(n^{3/2}), riffle permutations (321-, 2143-, and 2413-avoiding permutations) have superpatterns of size O(n), and the concatenations of sequences of riffles and their inverses have superpatterns of size O(nlog n). Our analysis includes a calculation of the leading constants in these bounds.

Recommendations

• Superpatterns and universal point sets
• Superpatterns and universal point sets
• Lower bounds for superpatterns and universal sequences
• Asymptotic bounds for permutations containing many different patterns
• Bounds on superpatterns containing all layered permutations

Cited in

(9)

• Patterns in colored circular permutations
• Rationality for subclasses of 321-avoiding permutations
• Superpatterns and universal point sets
• Pattern containment in circular permutations
• Superpatterns and universal point sets
• Critical properties of bipartite permutation graphs
• Dominance drawings for DAGs with bounded modular width
• Sorting via shuffles with a cut after the longest increasing prefix
• On planar straight-line dominance drawings

This page was built for publication: Small superpatterns for dominance drawing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5194761)