Rollercoasters and Caterpillars

Authors Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, Jeffrey Shallit



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.18.pdf
  • Filesize: 0.81 MB
  • 15 pages

Document Identifiers

Author Details

Therese Biedl
  • School of Computer Science, University of Waterloo, Canada
Ahmad Biniaz
  • School of Computer Science, University of Waterloo, Canada
Robert Cummings
  • School of Computer Science, University of Waterloo, Canada
Anna Lubiw
  • School of Computer Science, University of Waterloo, Canada
Florin Manea
  • Department of Computer Science, Kiel University, D-24098 Kiel, Germany
Dirk Nowotka
  • Department of Computer Science, Kiel University, D-24098 Kiel, Germany
Jeffrey Shallit
  • School of Computer Science, University of Waterloo, Canada

Cite AsGet BibTex

Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit. Rollercoasters and Caterpillars. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.18

Abstract

A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence - increasing or decreasing - has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an x-monotone polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, while the best known lower bound is Omega(n/log n). In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(n log n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,...,n} can be computed in O(n log log n) time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of maximum degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every n-vertex top-view caterpillar on every set of 25/3(n+4) points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is O(n log n). We also show that such a drawing can be obtained in linear time, when the points are given in sorted order.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
Keywords
  • sequences
  • alternating runs
  • patterns in permutations
  • caterpillars

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Tanbir Ahmed and Hunter Snevily. Some properties of roller coaster permutations. Bulletin of the Institute of Combinatorics and its Applications, 68:55-69, 2013. Google Scholar
  2. Nicolas Basset. Counting and generating permutations in regular classes. Algorithmica, 76(4):989-1034, 2016. Google Scholar
  3. Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit. Rollercoasters and caterpillars. CoRR, abs/1801.08565, 2018. URL: http://arxiv.org/abs/1801.08565.
  4. Therese C. Biedl, Timothy M. Chan, Martin Derka, Kshitij Jain, and Anna Lubiw. Improved bounds for drawing trees on fixed points with L-shaped edges. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD), volume 10692 of Lecture Notes in Computer Science, pages 305-317. Springer, 2017. Full version in arXiv:1709.01456. Google Scholar
  5. Maxime Crochemore and Ely Porat. Fast computation of a longest increasing subsequence and application. Information and Computation, 208(9):1054-1059, 2010. Google Scholar
  6. R. Ehrenborg and J. Jung. Descent pattern avoidance. Advances in Applied Mathematics, 49:375-390, 2012. Google Scholar
  7. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. Google Scholar
  8. Peter M. Fenwick. A new data structure for cumulative frequency tables. Software - Practice and Experience, 24(3):327-336, 1994. Google Scholar
  9. Michael L. Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. Google Scholar
  10. Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, Luca Grilli, and Marcus Krug. Orthogeodesic point-set embedding of trees. Computational Geometry: Theory and Applications, 46(8):929-944, 2013. Google Scholar
  11. John M. Hammersley. A few seedlings of research. In Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, pages 345-394. University of California Press, 1972. Google Scholar
  12. Sergey Kitaev. Patterns in Permutations and Words. Springer, 2011. Google Scholar
  13. S. Linton, N. Ruškuc, and V. Vatter, editors. Permutation Patterns. London Mathematical Society Lecture Note Series, vol. 376, Cambridge, 2010. Google Scholar
  14. Dan Romik. The Surprising Mathematics of Longest Increasing Subsequences. Cambridge, 2015. Google Scholar
  15. Manfred Scheucher. Orthogeodesic point set embeddings of outerplanar graphs. Master’s thesis, Graz University of Technology, 2015. Google Scholar
  16. N. J. A. Sloane et al. The On-Line Encylopedia of Integer Sequences. URL: https://oeis.org.
  17. J. Michael Steele. Variations on the monotone subsequence theme of Erdős and Szekeres. In David Aldous, Persi Diaconis, Joel Spencer, and J. Michael Steele, editors, Discrete Probability and Algorithms, pages 111-131. Springer New York, 1995. Google Scholar
  18. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6(3):80-82, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail