The Maximum Linear Arrangement Problem for trees under projectivity and planarity
A linear arrangement is a mapping $\pi$ from the $n$ vertices of a graph $G$ to $n$ distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the edges as semicircles above said line. In this setting, the length of an edge is defined as the absolute value of the difference between the positions of its two vertices in the arrangement, and the cost of an arrangement as the sum of all edge lengths. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In the planar variant for free trees, vertices have to be arranged in such a way that there are no edge crossings. In the projective variant for rooted trees, arrangements have to be planar and the root of the tree cannot be covered by any edge. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements, and show that caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby generalizing a previous extremal result on trees.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Bounds of the sum of edge lengths in linear arrangements of trees
A fundamental problem in network science is the normalization of the topological or physical distance between vertices, that requires understanding the range of variation of the unnormalized distances. Here we investigat…
Minimum projective linearizations of trees in linear time
The Minimum Linear Arrangement problem (MLA) consists of finding a mapping $\pi$ from vertices of a graph to distinct integers that minimizes $\sum_{\{u,v\}\in E}|\pi(u) - \pi(v)|$. In that setting, vertices are often as…
Rearrangement Events on Circular Genomes
Early literature on genome rearrangement modelling views the problem of computing evolutionary distances as an inherently combinatorial one. In particular, attention was given to estimating distances using the minimum nu…
Linking stem density, stem size and spatial arrangement: an approach to model discriminative self-thinning in even-aged forest stands
To model discriminative, i.e. competition induced, self-thinning in even-aged forest stands a concept has been explored that discriminative mortality alters spatial arrangement of trees which in turn alters the mortality…
UnityFinding high posterior density phylogenies by systematically extending a directed acyclic graph
Bayesian phylogenetics typically estimates a posterior distribution, or aspects thereof, using Markov chain Monte Carlo methods. These methods integrate over tree space by applying local rearrangements to move a tree thr…