×

Scaffold permutations. (English) Zbl 0668.05001

Author’s abstract: “The so-called in-order of the vertices of a binary tree T, as used in the data structure literature, is defined by the rule that each vertex follows all vertices of its left subtree, and precedes all those of its right subtree. Now, label the n vertices of T from 1 to n according to the shelling order, the root being labelled 1, the vertices at the same level being labelled consecutively from left to right, and among two levels the one closer to the root being labelled first. The permutation defined by taking the labels in the in-order of the vertices of T is called a Scaffold permutation. The Scaffold permutations on [1,n] are shown to form a code for the set of unlabelled binary trees with n vertices. The generalization of the Scaffold property to bipermutations on [1,n] generates a code for the set of rooted maximal planar maps with \(n+3\) vertices. Scaffold permutations and bipermutations afford some special features in the computation of their table of inversion, which is relevant to the Fraysseix-Pollack algorithm for embedding a planar map in the grid.”
Reviewer: J.Cigler

MSC:

05A05 Permutations, words, matrices
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] de Fraysseix, H.; Pach, J.; Pollack, R., Small sets supporting Fáry embedding of planar graphs, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 426-433 (1988)
[2] Hoffmann, K.; Mehlhorn, K.; Rosenstiehl, P.; Tarjan, R. E., Sorting Jordan sequences in linear time using level-linked search trees, (Information and Control, 68 (February-March 1986), Academic Press), 170-184, 1-3 · Zbl 0614.68051
[3] Knuth, D. E., Sorting and Searching, (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley Pub. Co), 11-13
[4] Sleator, D. D.; Tarjan, R. E., Self-adjusting binary trees, Proc. Fifteenth Annual ACM Symp. on Theory of Computing, 235-245 (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.