We study the atomic embeddability testing problem, which is a common generalization of clustered planarity ( c-planarity , for short) and thickenability testing, and present a polynomial-time algorithm for this problem, thereby giving the first polynomial-time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin’s work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally, we give a polynomial-time reduction from atomic embeddability to thickenability thereby showing that both problems are polynomially equivalent, and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

If a graph can be drawn on the torus so that every two independent edges cross an even number of times, then the graph can be embedded on the torus.

A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain a submatrix that can be turned into $P$ by changing some 1 entries to 0 entries, and changing an arbitrary 0 to 1 in $M$ introduces such a submatrix in $M$. In saturation problems for 0-1 matrices we are interested in estimating the minimum number of 1 entries in an $m \times n$ matrix that is saturating for $P$, in terms of $m$ and $n$. In other words, we wish to give good estimates for the saturation function of $P$. Recently, Brualdi and Cao [R. A. Brualdi and L. Cao, preprint, arXiv:2005.00379, 2020] initiated the study of saturation problems in the context of 0-1 matrices. We extend their work in several directions. We prove that every 0-1 forbidden matrix has its saturation function either in $\Theta(1)$ or $\Theta(n)$ in the case when we restrict ourselves to square saturating matrices. Then we give a partial answer to a question posed by Brualdi and Cao about the saturation function of $J_k$, which is obtained from the identity matrix $I_k$ by putting the first row after the last row. Furthermore, we exhibit a $5\times 5$ permutation matrix with the saturation function bounded from the above by a fixed constant. We complement this result by identifying large classes of 0-1 matrices with linear saturation function. Finally, we completely resolve the related semisaturation problem as far as the constant versus linear dichotomy is concerned.

We study the atomic embeddability testing problem, which is a common generalization of clustered planarity (c-planarity, for short) and thickenability testing, and present a polynomial time algorithm for this problem, thereby giving the first polynomial time algorithm for c-planarity. C-planarity was introduced in 1995 by Feng, Cohen, and Eades as a variant of graph planarity, in which the vertex set of the input graph is endowed with a hierarchical clustering and we seek an embedding (crossing free drawing) of the graph in the plane that respects the clustering in a certain natural sense. Until now, it has been an open problem whether c-planarity can be tested efficiently, despite relentless efforts. The thickenability problem for simplicial complexes emerged in the topology of manifolds in the 1960s. A 2-dimensional simplicial complex is thickenable if it embeds in some orientable 3-dimensional manifold. Recently, Carmesin announced that thickenability can be tested in polynomial time. Our algorithm for atomic embeddability combines ideas from Carmesin's work with algorithmic tools previously developed for weak embeddability testing. We express our results purely in terms of graphs on surfaces, and rely on the machinery of topological graph theory. Finally we give a polynomial-time reduction from c-planarity to thickenability and show that a slight generalization of atomic embeddability to the setting in which clusters are toroidal graphs is NP-complete.

A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing whether a piece-wise linear drawing of a planar graph G in the plane is approximable by an embedding can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class. In other words, we show that c-planarity with embedded pipes is tractable for graphs with prescribed combinatorial embedding. To the best of our knowledge, an analogous result was previously known essentially only when G is a cycle.

The \emph{genus} $\mathrm{g}(G)$ of a graph $G$ is the minimum $g$ such that $G$ has an embedding on the orientable surface $M_g$ of genus $g$. A drawing of a graph on a surface is \emph{independently even} if every pair of nonadjacent edges in the drawing crosses an even number of times. The \emph{$\mathbb{Z}_2$-genus} of a graph $G$, denoted by $\mathrm{g}_0(G)$, is the minimum $g$ such that $G$ has an independently even drawing on $M_g$. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Štefankovič proved that the $\mathbb{Z}_2$-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If $G=G_1\cup G_2$, $G_1$ and $G_2$ intersect in two vertices $u$ and $v$, and $G-u-v$ has $k$ connected components (among which we count the edge $uv$ if present), then $|\mathrm{g}_0(G)-(\mathrm{g}_0(G_1)+\mathrm{g}_0(G_2))|\le k+1$. For complete bipartite graphs $K_{m,n}$, with $n\ge m\ge 3$, we prove that $\frac{\mathrm{g}_0(K_{m,n})}{\mathrm{g}(K_{m,n})}=1-O(\frac{1}{n})$. Similar results are proved also for the Euler $\mathbb{Z}_2$-genus. We express the $\mathbb{Z}_2$-genus of a graph using the minimum rank of partial symmetric matrices over $\mathbb{Z}_2$; a problem that might be of independent interest.

A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t x t grid or one of the following so-called t-Kuratowski graphs: K_{3,t}, or t copies of K_5 or K_{3,3} sharing at most 2 common vertices. We show that the Z_2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z_2-genus, solving a problem posed by Schaefer and Stefankovic, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding φ : G → M of a graph G into a 2-manifold M maps the vertices in V (G) to distinct points and the edges in E (G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map φ : G → M comes from an embedding. A map φ : G → M is a weak embedding if it can be perturbed into an embedding ψε : G → M with ║φ – ψε║ < ε for every ε > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over ℤ2. It runs in O(π2ω) ≤ O(n4.75) time, where ω ≈ 2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually “untangles” the image φ(G) into an embedding ψ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a planar straight-line embedding that realizes these lengths; and G is extrinsically free in H if all constraints on the edge lengths of G depend on G only, irrespective of additional edges of the host H.

The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani–Tutte theorem in the case when each cluster induces a connected subgraph.Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

A topological graph drawn on a cylinder whose base is horizontal is angularly monotone if every vertical line intersects every edge at most once. Let $c(n)$ denote the maximum number $c$ such that every simple angularly monotone drawing of a complete graph on $n$ vertices contains at least $c$ pairwise disjoint edges. We show that for every simple complete topological graph $G$ there exists $\Delta$, $0<\Delta

A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. We present a novel tool for finding crossing free subgraphs in simple topological graphs. Using this tool, we solve the following two problems. Let G be a complete simple topological graph on n vertices. The three edges induced by any triplet of vertices in G form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an empty triangle. In 1998, Harborth proved that G has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least 2n/3. We settle Harborth's conjecture in the affirmative.

We consider graphs that admit polyline drawings where all crossings occur at the same angle $\alpha\in (0,\frac{\pi}{2}]$. We prove that every graph on n vertices that admits such a polyline drawing with at most two bends per edge has $O(n)$ edges. This result remains true when each crossing occurs at an angle from a small set of angles. We also provide several extensions that might be of independent interest.

What is the smallest number τ = τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following: