Polygons Drawn from Permutations

• Autorzy: Bilotta S. , Rinaldi S. , Socci S.
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π₁, π₂). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π₂(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π₁(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π₁(P) = π.

Słowa kluczowe

EN

permutations; polyominoes

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 3/4
• Strony: 329--342
• Opis fizyczny: Bibliogr. 16 poz., wykr.

Twórcy

autor

Bilotta S.

• Dipartimento di Sistemi e Informatica, Universitá di Firenze, Viale Morgagni 65, 50134, Firenze, Italy

autor

Rinaldi S.

• Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universitá di Siena, Via Roma 56, 53100, Siena, Italy

autor

Socci S.

• Dipartimento di Ingegneria Informatica e Scienze Matematiche, Universitá di Siena, Via Roma 56, 53100, Siena, Italy

Bibliografia

• [1] Albert, M., Linton, S., Ruskuc, N., Waton, S., On convex permutations, Disc. Math. 311 (2011) 715-722.
• [2] Bajuelos A, L., Martins A. M., Vertex Guards in a Subclass of Orthogonal Polygons, International Journal of Computer Science and Network Security (IJCSNS) 6, No. 9A (2006) 102-108.
• [3] Bajuelos A. L., Mafalda A.M., Characterizing and Covering Some Subclasses of Orthogonal Polygons, Computational Science ICCS 2006: 6th International Conference, Lecture Notes in Computer Science (LNCS) 3992, Springer-Verlag (2006) 255-262.
• [4] Tomas A. P., Bajuelos A. L., Generating Random Orthogonal Polygons, Current Topics in Artificial Intelligence: 10th Conf. of the Spanish Association for Artificial Intelligence, CAEPIA 2003, and 5th Conference on Technology Transfer, TTIA 2003 Lecture Notes in Computer Science (LNCS) 3040, Springer-Verlag (2004) 364-373.
• [5] Beaton, N., Disanto, F., Guttmann, A.J., Rinaldi, S., On the enumeration of column-convex permutominoes, 23th Formal Power Series and Algebraic Combinatorics, Proc. of Disc. Math. Theor. Comp. Sci., AO (2011) 111-122.
• [6] Bernini, A., Disanto, F., Pinzani, R., Rinaldi, S., Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) Article 07.9.7.
• [7] Boldi, P., Lonati, V., Radicioni, R., Santini, M., The number of convex permutominoes, Inf. Comp. 206 (2008) 1074-1083.
• [8] Disanto, F., Duchi, E., Pinzani, R., Rinaldi, S., Polyominoes determined by permutations: enumeration via bijections, Ann. Comb. 16 (2012), to appear.
• [9] Disanto, F., Frosini, A., Pinzani, R., Rinaldi, S., A closed formula for the number of convex permutominoes, El. J. Combinatorics 14 (2007) Article R57.
• [10] Duchi, E., Poulalhon, D., On square permutations, Fifth Colloquium on Mathematics and Computer Science, Proc. of Disc. Math. Theor. Comp. Sci., AI (2008) 207-222.
• [11] Eppstein, D., The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing, Graph Drawing, Lecture Notes in Computer Science Volume (LNCS) 5417 (2009) 78-89.
• [12] Fanti, I., Frosini, A., Grazzini, E., Pinzani, R., Rinaldi, S., Characterization and enumeration of some classes of permutominoes, Pure Math. App., Vol. 18 No. 3-4 265-290 (2007).
• [13] Incitti, F., Permutation diagrams, fixed points and Kazdhan-Lusztig ^-polynomials, Ann. Comb. 10 (2006) 369-387.
• [14] Mansour, T., Severini, S., Grid polygons from permutations and their enumeration by the kernel method, 19th International Conference on Formal Power Series and Algebraic Combinatorics, Tianjin, China, July 2-6, 2007.
• [15] Kassel, C., Lascoux, A., Reutenauer, C., The singular locus of a Schubert variety, J. Algebra 269 (2003) 74-108.
• [16] Sloane, N.J.A., The On-Line Encyclopedia of Integer Sequences, available on line at http://www.research.att.com/ ~njas/sequences/