[ca] Una aproximació exitosa per representar l'estructura sintàctica de les frases en Lingüística Computacional, basada en la teoria desenvolupada per Tesnière, és la d'un arbre de dependències sintàctiques. Parelles de vèrtexs de paraules relacionades sintàcticament s'uneixen per una aresta que porta una etiqueta que indica el tipus de relació sintàctica. Quan abstraiem les paraules i les relacions sintàctiques, eliminant les etiquetes dels vèrtexs i les etiquetes de les arestes que indiquen el tipus de relació sintàctica, obtenim el que es coneix com un arbre linearitzat. Un arbre linearitzat és simplement un arbre arrelat juntament amb un arranjament lineal. I un arranjament lineal d'un graf és una permutació dels vèrtexs del graf, el qual es pot representar dibuixant els vèrtexs en una línia horitzontal i les arestes com a semicercles per sobre d'ella. Hi ha molts problemes computacionals que involucren arranjaments lineals de grafs. Exemples notables són aquells que busquen una disposició que optimitzi la suma de les longituds de les arestes, on la longitud d'una aresta es defineix com el valor absolut de la diferència de les posicions dels extrems de l'aresta en l'arranjament. El problema que minimitza aquesta suma és conegut com el problema de l'Arranjament Lineal mínim (minLA). Quan es maximitza la suma de les longituds de les arestes, el problema es coneix com el problema de l'Arranjament Lineal Màxim (MaxLA). En un intent de proporcionar una teoria de l'ordre de les paraules, els investigadors en llenguatge humà han proposat el conegut principi de minimització de la Distància de Dependències després d'observar i proporcionar evidència a gran escala de la tendència de les llengües a minimitzar la suma total de les longituds de les arestes en els arbres de dependències sintàctiques de les seves frases. Per tal de proporcionar una teoria exhaustiva de l'ordre de les paraules, alguns investigadors en llenguatge també han argumentat que MaxLA es manifesta en les llengües en subestructures dels arbres de dependències sintàctiques isomorfes a un graf estrella. Se sap que tant minLA com MaxLA són NP-Difícils en grafs generals, i només es coneixen algorismes polinòmics per arbres en minLA. En aquesta tesi, aportem algorismes òptims per resoldre diverses variants restringides tant de minLA com de MaxLA. Estudiem aquests dos problemes per a grafs bipartits sota la restricció que els vèrtexs han de ser disposats en dos intervals disjunts segons la partició de vèrtexs a què pertanyen (arranjaments bipartits). També els estudiem per a arbres lliures sota la restricció que les arestes no puguin creuar-se en l'arranjament (arranjaments planars), i per a arbres arrelats sota la restricció que l'arranjament és planar i la arrel no està coberta (arranjaments projectius). En aquesta tesi també s'estudia la formulació no restringida de MaxLA per a arbres lliures. Els nostres esforços han produït solucions en temps polinòmic per a arbres k-lineals (0<= k <= 2) i un algorisme d'aproximació 3/2. A més, proveïm fórmules i algorismes per calcular el valor esperat del cost d'un arranjament bipartit aleatori uniforme de grafs bipartits, i d'arranjaments planars i projectius d'arbres (també aleatoris uniformes), basant-nos en nous coneixements sobre com generar aquests arranjaments uniformement a l'atzar. Tots aquests algorismes, i d'altres també, s'han empaquetat dins la Llibreria d'Arranjaments Lineals (LAL), amb llicència GNU Affero GPL.

[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.