The genus of the binomial random graph $G(n,p)$ is well understood for a wide range of $p=p(n)$. Recently, the study of the genus of the random bipartite graph $G(n_1,n_2,p)$, with partition classes of size $n_1$ and $n_2$, was initiated by Mohar and Jing, who showed that when $n_1$ and $n_2$ are comparable in size and $p=p(n_1,n_2)$ is significantly larger than $(n_1n_2)^{-\frac{1}{2}}$ the genus of the random bipartite graph has a similar behavior to that of the binomial random graph. In this paper we show that there is a threshold for planarity of the random bipartite graph at $p=(n_1n_2)^{-\frac{1}{2}}$ and investigate the genus close to this threshold, extending the results of Mohar and Jing. It turns out that there is qualitatively different behavior in the case where $n_1$ and $n_2$ are comparable, when with high probability (whp) the genus is linear in the number of edges, than in the case where $n_1$ is asymptotically smaller than $n_2$, when whp the genus behaves like the genus of a sparse random graph $G(n_1,q)$ for an appropriately chosen $q=q(p,n_1,n_2)$.

It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded as a function of the genus of the graph $g(G)$. The best known bound, that $c(G) \leq \left\lfloor \frac{3 g(G)}{2}\right\rfloor + 3$, was given by Schröder, who conjectured that in fact $c(G) \leq g(G) + 3$. We give the first improvement to Schröder's bound, showing that $c(G) \leq \frac{4g(G)}{3} + \frac{10}{3}$.

Many of the tools developed for the theory of tree-decompositions of graphs do not work for directed graphs. In this paper we show that some of the most basic tools do work in the case where the model digraph is a directed path. Using these tools we define a notion of a directed blockage in a digraph and prove a min-max theorem for directed path-width analogous to the result of Bienstock, Roberston, Seymour, and Thomas for blockages in graphs. Furthermore, we show that every digraph with directed path width $\geq k$ contains each arboresence of order $\leq k + 1$ as a butterfly minor. Finally we also show that every digraph admits a linked directed path-decomposition of minimum width, extending a result of Kim and Seymour on semi-complete digraphs.

As a major step in their proof of Wagner's conjecture, Robertson and Seymour showed that every graph not containing a fixed graph $H$ as a minor has a tree-decomposition in which each torso is almost embeddable in a surface of bounded genus. Recently, Grohe and Marx proved a similar result for graphs not containing $H$ as a topological minor. They showed that every graph which does not contain $H$ as a topological minor has a tree-decomposition in which every torso is either almost embeddable in a surface of bounded genus or has a bounded number of vertices of high degree. We give a short proof of the theorem of Grohe and Marx, improving their bounds on a number of the parameters involved.

We prove a duality theorem applicable to a wide range of specializations, as well as to some generalizations, of tangles in graphs. It generalizes the classical tangle duality theorem of Robertson and Seymour, which says that every graph has either a large-order tangle or a certain low-width tree-decomposition witnessing that it cannot have such a tangle. Our result also yields duality theorems for profiles and for $k$-blocks. This solves a problem studied, but not solved, by Diestel and Oum and answers an earlier question of Carmesin, Diestel, Hamann, and Hundertmark.

Roberston and Seymour introduced tangles of order $k$ as objects representing highly connected parts of a graph and showed that every graph admits a tree-decomposition of adhesion $<\!k$ in which each tangle of order $k$ is contained in a different part. Recently, Carmesin, Diestel, Hamann, and Hundertmark showed that such a tree-decomposition can be constructed in a canonical way, which makes it invariant under automorphisms of the graph. These canonical tree-decompositions necessarily have parts which contain no tangle of order $k$, which we call inessential. Diestel asked what could be said about the structure of the inessential parts. In this paper we show that the torsos of the inessential parts in these tree-decompositions have branch-width $<\!k$, allowing us to further refine the canonical tree-decompositions and also show that a similar result holds for $k$-blocks. We also use our methods to further refine the essential parts in such a tree-decomposition in a similar fashion.