Abstract. A graph [Formula: see text] is Ramsey for a pair of graphs [Formula: see text] if any red/blue-coloring of the edges of [Formula: see text] yields a copy of [Formula: see text] with all edges colored red or a copy of [Formula: see text] with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case [Formula: see text], received considerable attention. This led to the open question whether there are connected graphs [Formula: see text] and [Formula: see text] such that [Formula: see text] and [Formula: see text] are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several nontrivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form [Formula: see text], where [Formula: see text] is a tree and [Formula: see text] is a complete graph. We show that if [Formula: see text] belongs to a certain family of trees, including all nontrivial stars, then [Formula: see text] is Ramsey equivalent to a family of pairs of the form [Formula: see text], where [Formula: see text] is obtained from [Formula: see text] by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for [Formula: see text] to be Ramsey equivalent to [Formula: see text], [Formula: see text] must have roughly this form. On the other hand, we prove that for many other trees [Formula: see text], including all odd-diameter trees, [Formula: see text] is not equivalent to any such pair, not even to the pair [Formula: see text], where [Formula: see text] is a complete graph [Formula: see text] with a single edge attached.

A graph is 2-degenerate if every subgraph contains a vertex of degree at most 2. We show that every 2-degenerate graph can be drawn with straight lines such that the drawing decomposes into 4 plane forests. Therefore, the geometric arboricity, and hence the geometric thickness, of 2-degenerate graphs is at most 4. On the other hand, we show that there are 2-degenerate graphs that do not admit any straight-line drawing with a decomposition of the edge set into 2 plane graphs. That is, there are 2-degenerate graphs with geometric thickness, and hence geometric arboricity, at least 3. This answers two questions posed by Eppstein [Separating thickness from geometric thickness. In Towards a Theory of Geometric Graphs, vol. 342 of Contemp. Math., AMS, 2004].

Laman graphs are the minimally rigid graphs in the plane. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O(n^(3/2)) and a more complicated algorithm with running time O(n log^3 n) based on involved planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465 - 497, 1992] with running time O(n sqrt{n log n}). To solve this problem we introduce two algorithms (with the running times stated above) that check whether for a directed planar graph G, disjoint sets S, T subseteq V(G), and a fixed k the following connectivity condition holds: for each vertex s in S there are k directed paths from s to T pairwise having only vertex s in common. This variant of connectivity seems interesting on its own.