We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph D can be augmented with (any number of) arcs X such that D+X is strongly connected, but still plane and oriented, is NP-hard. The hardness also holds for the planar variant. This question becomes trivial within plane (or planar) digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted variant, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph D along with some integer k, and asks for an X of size at most k ensuring that D+X is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n² log n. The cornerstone of our procedure is a structural result showing that, for any fixed k, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a randomized reduction to the polynomial Minimum Dijoin problem, yielding a Monte-Carlo FPT algorithm, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.

The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph $G$ and a parameter $k$, one has to decide if there is a set $S$ of at most $k$ vertices such that $G-S$ is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time $2^{o(k)}n^{\mathcal{O}(1)}$ in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such $2^{o(k)}n^{\mathcal{O}(1)}$ algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time $2^{k^\varepsilon} \mathop{\rm poly}(n)$, for some $\varepsilon<1$, where $n$ denotes the number of vertices of the instance and $k$ the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of ``thin'' objects like segment graphs or more generally $s$-string graphs.

In the $K_r$-Cover problem, given a graph $G$ and an integer $k$ one has to decide if there exists a set of at most $k$ vertices whose removal destroys all $r$-cliques of $G$. In this paper we give an algorithm for $K_r$-Cover that runs in subexponential FPT time on graph classes satisfying two simple conditions related to cliques and treewidth. As an application we show that our algorithm solves $K_r$-Cover in time * $2^{O_r\left (k^{(r+1)/(r+2)}\log k \right)} \cdot n^{O_r(1)}$ in pseudo-disk graphs and map-graphs; * $2^{O_{t,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $K_{t,t}$-subgraph-free string graphs; and * $2^{O_{H,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $H$-minor-free graphs.

Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph $G$ is the minimum integer $d$ such that $G$ can be represented as a touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion.

We study the complexity of deciding whether a given digraph D=(V,A) admits a partition (A1,A2) of its arc set such that each of the corresponding digraphs D1=(V,A1) and D2=(V,A2) satisfy some given prescribed property. We mainly focus on the following 15 properties: being bipartite, being connected, being strongly connected, being acyclic (spanning or not necessarily spanning), containing an in-branching, containing an out-branching, having some in-degree (or out-degree) conditions, satisfying some conditions on the number of arcs, being balanced (connected or not) or being a cycle. Combined with previous research, our work leads to a complete classification (in terms of being polynomial or NP-complete) of the complexity of 120 arc-partitioning problems on digraphs.

We show that if a planar graph G has a plane straight-line drawing in which a subset S of its vertices are collinear, then for any set of points, X, in the plane with |X| = |S|, there is a plane straight-line drawing of G in which the vertices in S are mapped to the points in X. This solves an open problem posed by Ravsky and Verbitsky in 2008. In their terminology, we show that every collinear set is free. This result has applications in graph drawing, including untangling, column planarity, universal point subsets, and partial simultaneous drawings.

The ⌞-intersection graphs are the graphs that have a representation as intersection graphs of axis-parallel ⌞ shapes in the plane. A subfamily of these graphs are {⌞, |, –}-contact graphs which are the contact graphs of axis parallel ⌞, |, and – shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are ⌞-intersection graphs, and that triangle-free planar graphs are {⌞, |, –}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.

In this paper, we conclude the calculation of the domination number of all [Formula: see text] grid graphs. Indeed, we prove Chang’s conjecture saying that for every [Formula: see text], [Formula: see text].

Given a set S of segments in the plane, the intersection graph of S is the graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar graph is the intersection graph of some segments in the plane.

An outerplanar graph is a planar graph that can be embedded in the plane without crossing edges, in such a way that all the vertices are on the outer boundary. In this paper, we prove a conjecture of Chartrand, Geller, and Hedetniemi that any planar graph G=(V,E) has a bipartition of its edge set E = A ∪ B such that the graphs induced by these subsets, G[A] and G[B], are outerplanar.