[en] A successful approach to represent the syntactic structure of sentences in Computational Linguistics, founded in the theory developed by Tesnière, is that of syntactic dependency tree. Pairs of vertices of syntactically-related words are joined with an edge that carries a label which indicates the type of syntactic relationship. When words and syntactic relationships are abstracted away, by removing the vertex labels and removing the edge labels with the type of syntactic relationship, we are left with a so-called linearized tree. A linearized tree is simply a rooted tree in conjunction with a linear arrangement. And a linear arrangement of a graph is a permutation of the graph's vertices, and can be represented by drawing the vertices on a horizontal line and the edges as semicircles above it. There exist many computational problems that involve linear arrangements of graphs. Remarkable examples are those that look for an arrangement that optimize the sum of edge lengths, where the length of an edge is defined as the absolute value of the difference of the positions of the endpoints of the edge in the arrangement. The problem that minimizes this sum is known as the minimum Linear Arrangement problem (minLA). When one maximizes the sum of edge lengths, the problem is known as the Maximum Linear Arrangement problem (MaxLA). In an attempt to provide a theory of word order, language researchers put forward the now well-known Dependency Distance minimization principle after observing and providing large-scale evidence of the tendency in languages to minimize the total sum of edge lengths in the syntactic dependency trees of their sentences. In order to provide an exhaustive theory of word order, some language researchers have also argued that MaxLA manifests itself in languages in substructures of the syntactic dependency trees isomorphic to a star graph. Both minLA and MaxLA are known to be NP-Hard on general graphs, and only minLA is known to be solvable in polynomial time on trees and other classes of graphs. In this thesis we contribute with optimal algorithms to solve several constrained variants of both minLA and MaxLA. We study these two problems for bipartite graphs under the constraint that vertices have to be arranged in two disjoint intervals according to the vertex partition they belong (bipartite arrangements). These are also studied for free trees under the constraint that edges are not allowed to cross in the arrangement (planar arrangements), and for rooted trees under the constraint that the arrangement is planar and the root is not covered (projective arrangements). We also tackle the unconstrained formulation of MaxLA for free trees. Our efforts have yielded polynomial-time solutions for k-linear trees (0 <= k <= 2) and a 3/2-approximation algorithm. Furthermore, we devise algorithms and derive formulas to calculate the expected value of the cost of bipartite arrangements of bipartite graphs, and planar and projective arrangements of trees, based on new knowledge on how to generate such arrangements uniformly at random. All these algorithms, and others as well, have been packaged into the Linear Arrangement Library (LAL), licensed under the GNU Affero GPL.

[es] Una aproximación exitosa para representar la estructura sintáctica de las frases en Lingüística Computacional, basada en la teoría desarrollada por Tesnière, es la de un árbol de dependencias sintácticas. Parejas de vértices de palabras relacionadas sintácticamente se unen por una arista que lleva una etiqueta que indica el tipo de relación sintáctica. Cuando abstraemos las palabras y las relaciones sintácticas, eliminando las etiquetas de los vértices y las etiquetas de las aristas que indican el tipo de relación sintáctica, obtenemos lo que se conoce como un árbol linearizado. Un árbol linearizado es simplemente un árbol con raíz cuyos vértices se han distribuido en una ordenación lineal. Y una ordenación lineal de los vértices de un grafo es una permutación de los vértices del grafo, la cual se puede representar dibujando los vértices en una línea horizontal y las aristas como semicírculos por encima de ella. Existen muchos problemas computacionales que involucran ordenaciones lineales de grafos. Ejemplos notables son aquellos que buscan una ordenación que optimice la suma de las longitudes de las aristas, donde la longitud de una arista se define como el valor absoluto de la diferencia de las posiciones de los extremos de la arista en la ordenación. El problema que minimiza esta suma es conocido como el problema de la Ordenación Lineal mínima (minLA). Cuando se maximiza la suma de las longitudes de las aristas, el problema se conoce como el problema de la Ordenación Lineal Máxima (MaxLA). En un intento de proporcionar una teoría del orden de las palabras, los investigadores en lenguaje humano han propuesto el conocido principio de minimización de la Distancia de Dependencias después de observar y proporcionar evidencia a gran escala de la tendencia de las lenguas a minimizar la suma total de las longitudes de las aristas en los árboles de dependencias sintácticas de sus frases. A fin de proporcionar una teoría exhaustiva del orden de las palabras, algunos investigadores en lenguaje también han argumentado que MaxLA se manifiesta en las lenguas en subestructuras de los árboles de dependencias sintácticas isomorfas en un grafo estrella. Se sabe que tanto minLA como MaxLA son NP-Difíciles en grafos generales, y sólo se conocen algoritmos polinómicos para árboles en minLA. En esta tesis, aportamos algoritmos óptimos para resolver diversas variantes restringidas tanto de minLA como de MaxLA. Estudiamos estos dos problemas para grafos bipartitos bajo la restricción de que los vértices deben ser dispuestos en dos intervalos disjuntos según la partición de vértices a los que pertenecen (ordenaciones bipartitas). También los estudiamos para árboles libres bajo la restricción de que las aristas no puedan cruzarse en la ordenación (ordenaciones planares), y para árboles arraigados bajo la restricción que la ordenación es planar y la raíz no está cubierta (ordenaciones proyectivas). En esta tesis se estudia también la formulación no restringida de MaxLA para árboles libres. Nuestros esfuerzos han producido soluciones en tiempo polinómico para árboles k-lineales (0 <= k <= 2) y un algoritmo de aproximación 3/2. Además, proveemos fórmulas y algoritmos para calcular el valor esperado del coste de una ordenación bipartita aleatorio uniforme de grafos bipartitos, y de ordenaciones planares y proyectivas de árboles (también aleatorios uniformes), basándonos en nuevos conocimientos sobre cómo generar estas ordenaciones uniformemente al azar. Todos estos algoritmos, y otros también, se han empaquetado en la Librería de Ordenaciones Lineales (LAL), con licencia GNU Affero GPL.