Search Results

A permutation π: [n] → [n] is a Baxter permutation if and only if it does not contain either of the patterns 2-41-3 and 3-14-2. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using o(n) additional bits from their information-theoretical lower bounds) for Baxter permutations of size n that supports π(i) and π^{-1}(j) queries for any i ∈ [n] in O(f₁(n)) and O(f₂(n)) time, respectively. Here, f₁(n) and f₂(n) are arbitrary increasing functions that satisfy the conditions ω(log n) and ω(log² n), respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations. The main idea is to traverse the Cartesian tree on the permutation using a simple yet elegant two-stack algorithm which traverses the nodes in ascending order of their corresponding labels and stores the necessary information throughout the algorithm. Additionally, we consider a subclass of Baxter permutations called separable permutations, which do not contain either of the patterns 2-4-1-3 and 3-1-4-2. In this paper, we provide the first succinct representation of the separable permutation ρ: [n] → [n] of size n that supports both ρ(i) and ρ^{-1}(j) queries in O(1) time. In particular, this result circumvents Golynski’s [SODA 2009] lower bound result for trade-offs between redundancy and ρ(i) and ρ^{-1}(j) queries. Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently.