Petr Hliněný

Zdeněk Dvořák, Petr Hliněný, Bojan Mohar

We study $c$-crossing-critical graphs, which are the minimal graphs that require at least $c$ edge-crossings when drawn in the plane. For $c=1$ there are only two such graphs without degree-2 vertices, $K_5$ and $K_{3,3}$, but for any fixed $c>1$ there exist infinitely many $c$-crossing-critical graphs. It has been previously shown that $c$-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every $c$-crossing-critical graph can be obtained from a $c$-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the $c$-crossing-critical graphs of at most given order $n$ in polynomial time per each generated graph.

Éric Colin de Verdière, Petr Hliněný

The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework yielding fixed-parameter tractable (FPT) algorithms for many generalized crossing number problems. Our framework takes the following form. We fix a surface S and a class D of "allowed" topological drawings of graphs in S (e.g., some class of drawings with at most t crossings). We assume that testing membership in D can be done algorithmically, and that restricting a drawing in D, extending it without adding any crossing, or transforming it with a self-homeomorphism of S yields a drawing that is also in D. Then deciding whether an input graph G has a drawing in D, and computing one if it is the case, is fixed-parameter tractable in (essentially) the genus of S and the maximum number of crossings in a drawing in D. More generally, we may take as input an edge-colored graph and distinguish crossings by the colors of the involved edges; and we may allow a bounded number of edge removals and vertex splits on G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This implies, in a unified way, linear or quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle's metatheorem, but our algorithms have a better runtime. Moreover, our framework extends to these crossing number variants in any fixed surface, and also allows us to fix the rotation system of the drawing of a graph in some variants.

Petr Hliněný, Jan Jedelský

We introduce H-clique-width, a new structural measure of graphs that aims to provide a hereditary analogue of the traditional graph product structure. The definition naturally generalises the ordinary clique-width concept. As a result, for a class H of graphs (such as the class of paths), the H-clique-width of a graph G equals the least integer t such that G is isomorphic to an induced subgraph of the strong product of a graph from H and a graph of clique-width t. We study basic properties of H-clique-width and compare it to other established structural parameters of graphs. Notably, we prove that the celebrated Planar graph product structure theorem by Dujmovic et al., and related graph product structure results, can all be formulated with the induced subgraph containment relation. In particular, every planar graph is isomorphic to an induced subgraph of the strong product of a path and a graph of tree-width 39.