We present fixed-parameter algorithms (FPT algorithms) for the \(\lambda\)-vertex connectivity augmentation (\(\lambda\)-VCA) problem for all values of \(\lambda \le 4\); that is, we give an algorithm that given a graph \(G\), a set \(L\) of non-edges, and an integer \(k\), determines in time \(k^{\mathcal{O}(k)} \cdot n^{c}\) (for some constant \(c\) independent of \(k\)) whether \(G\) can be made \(\lambda\)-vertex connected by adding at most \(k\) elements from \(L\).

We develop a structural approach to simultaneous embeddability in temporal sequences of graphs, inspired by graph minor theory. Our main result is a classification theorem for 2-connected temporal sequences: we identify five obstruction classes and show that every 2-connected temporal sequence is either simultaneously embeddable or admits a sequence of improvements leading to an obstruction. This structural insight leads to a polynomial-time algorithm for deciding the simultaneous embeddability of 2-connected temporal sequences.

A weak deletion sequence is a sequence ( G 1 , … , G n ) of graphs so that for each i ∈ [ n − 1 ] either G i is isomorphic to a subgraph of G i + 1 , or vice versa: G i + 1 is isomorphic to a subgraph of G i . We prove that determining the simultaneous planar embeddability of weak deletion sequences of 2-connected graphs is NP-hard.

We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or obtained from a biclique by turning one side into a triangle. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte’s wheel theorem.

A $k$-block in a graph $G$ is a maximal set of at least $k$ vertices no two of which can be separated in $G$ by fewer than $k$ other vertices. The block number $\beta(G)$ of $G$ is the largest integer $k$ such that $G$ has a $k$-block. We investigate how $\beta$ interacts with density invariants of graphs, such as their minimum or average degree. We further present algorithms that decide whether a graph has a $k$-block, or which find all its $k$-blocks. The connectivity invariant $\beta(G)$ has a dual width invariant, the block-width ${\rm bw}(G)$ of $G$. Our algorithms imply the duality theorem $\beta = {bw}$: a graph has a block-decomposition of width and adhesion $< k$ if and only if it contains no $k$-block.