The Minimum Linear Arrangement problem (MLA) consists of finding a mapping π from vertices of a graph to distinct integers that minimizes ∑{u,v}∈E|π(u)−π(v)|. In that setting, vertices are often assumed to lie on a horizontal line and edges are drawn as semicircles above said line. For trees, various algorithms are available to solve the problem in polynomial time in n=|V|. There exist variants of the MLA in which the arrangements are constrained. Iordanskii, and later Hochberg and Stallmann (HS), put forward O(n)-time algorithms that solve the problem when arrangements are constrained to be planar (also known as one-page book embeddings). We also consider linear arrangements of rooted trees that are constrained to be projective (planar embeddings where the root is not covered by any edge). Gildea and Temperley (GT) sketched an algorithm for projective arrangements which they claimed runs in O(n) but did not provide any justification of its cost. In contrast, Park and Levy claimed that GT's algorithm runs in O(nlog⁡dmax) where dmax is the maximum degree but did not provide sufficient detail. Here we correct an error in HS's algorithm for the planar case, show its relationship with the projective case, and derive simple algorithms for the projective and planar cases that run without a doubt in O(n) time.

More than 30 years ago, Shiloach published an algorithm to solve the minimum linear arrangement problem for undirected trees. Here we fix a small error in the original version of the algorithm and discuss its effect on subsequent literature. We also improve some aspects of the notation.

An exponential lower bound for the size of tree-like cutting planes refutations of a certain family of conjunctive normal form (CNF) formulas with polynomial size resolution refutations is proved. This implies an exponential separation between the tree-like versions and the dag-like versions of resolution and cutting planes. In both cases only superpolynomial separations were known [A. Urquhart, Bull. Symbolic Logic, 1 (1995), pp. 425--467; J. Johannsen, Inform. Process. Lett., 67 (1998), pp. 37--41; P. Clote and A. Setzer, in Proof Complexity and Feasible Arithmetics, Amer. Math. Soc., Providence, RI, 1998, pp. 93--117]. In order to prove these separations, the lower bounds on the depth of monotone circuits of Raz and McKenzie in [ Combinatorica, 19 (1999), pp. 403--435] are extended to monotone real circuits. An exponential separation is also proved between tree-like resolution and several refinements of resolution: negative resolution and regular resolution. Actually, this last separation also provides a separation between tree-like resolution and ordered resolution, and thus the corresponding superpolynomial separation of [A. Urquhart, Bull. Symbolic Logic, 1 (1995), pp. 425--467] is extended. Finally, an exponential separation between ordered resolution and unrestricted resolution (also negative resolution) is proved. Only a superpolynomial separation between ordered and unrestricted resolution was previously known [A. Goerdt, Ann. Math. Artificial Intelligence, 6 (1992), pp. 169--184].

We prove an exponential lower bound for tree-like cutting planes refutations of a set of clauses which has polynomial size resolution refutations. This implies an exponential separation between tree-like and dag-like proofs for both cutting planes and resolution; in both cases only superpolynomial separations were known before. In order to prove this, we extend the lower bounds on the depth of monotone circuits of R. Raz and P. McKenzie (1997) to monotone real circuits. In the case of resolution, we further improve this result by giving an exponential separation of tree-like resolution front (dag-like) regular resolution proofs. In fact, the refutation provided to give the upper bound respects the stronger restriction of being a Davis-Puatam resolution proof. Finally, we prove an exponential separation between Davis-Putnam resolution and unrestricted resolution proofs; only a superpolynomial separations was previously known.