Planarizing matchings
The drawing below shows the Petersen graph (blue vertices), with order-six dihedral symmetry rather than the order-10 symmetry that you’re probably more used to. Three edges are highlighted by shaded ovals surrounding them; these edges form a matching, a set of edges that don’t touch each other. If you contract these edges, you get a graph with seven vertices: the three ovals and the remaining four blue vertices. This seven-vertex graph is planar, because all of the Petersen graph’s crossings are hidden inside the ovals. It turns out that, whenever you can contract a matching to make the resulting graph planar, the graph you started out with (here, the Petersen graph) is a string graph. This means that we can draw a curve in the plane (called a string) for each vertex of \(G\), so that two strings intersect if and only if the corresponding vertices are adjacent. Strings are allowed to intersect any number of times, not just once.
The figure below shows how to construct strings (the curves in various shades of red) for the Petersen graph. Start with a drawing of the contracted planar graph. Expand each contracted supervertex to an oval, large enough to contain both endpoints of the contracted edge, which you can place anywhere inside the oval. You can undo the contraction in this way, keeping all crossings confined inside the ovals. Now, place subdivision points on each non-contracted edge (the green tick marks of the figure), splitting it into two half-edges. Draw strings that trace around each uncontracted vertex and its incident half-edges. These strings will automatically cross near the green subdivision points and can also be made to cross within each oval, so that two strings cross exactly when the vertices they trace around are adjacent.
One of my recent preprints, “String graph obstacles of high girth and of bounded degree” (arXiv:2509.00278, with Maria Chudnovsky and Princeton student David Fischer, to appear at the International Symposium on Graph Drawing) is mainly about “obstacles”, graphs whose presence inside another graph prevents it from being a string graph. More technically these are graphs that that are not themselves string graphs, but for which removing any vertex or contracting any edge produces a string graph. If there were finitely many obstacles (as there are for planar graphs, the two graphs \(K_5\) and \(K_{3,3}\)) we might hope for a fast algorithm to recognize string graphs by looking for obstacles, but unfortunately it’s been known for a long time that there are infinitely many. One of our main results is that, even among sparse and nearly-planar graphs (graphs that are only one edge away from being planar), there are infinitely many of these obstacles.
Some of our results use a lemma that you can recognize subcubic string graphs using planarizing matchings: a graph with maximum degree three is a string graph if and only if it has a planarizing matching. We also show that it is possible to find planarizing matchings in linear time for graphs of bounded treewidth (regardless of their degree). Therefore, we get an algorithm that can recognize subcubic string graphs of bounded treewidth in linear time, interesting because the more general problem of recognizing string graphs that are not necessarily subcubic is \(\mathsf{NP}\)-complete. Unusually, the difficult part about proving \(\mathsf{NP}\)-completeness (by Schaefer, Sedgwick, and Štefankovič in 2003) was proving that the problem belongs to \(\mathsf{NP}\), not obvious because some string graphs require an exponential number of crossings in their string representations.
This naturally raises the question: to find planarizing matchings in subcubic graphs, do we need to assume bounded treewidth? Or is there maybe a polynomial time algorithm for planarizing matchings in subcubic graphs, without that assumption? I don’t know. The closest I was able to get to an answer to this is a sketch of an \(\mathsf{NP}\)-completeness proof for finding planarizing matchings in graphs of maximum degree five. It’s not in the preprint, though, so maybe I should include it here.
It is a reduction from nondeterministic constraint logic (NCL), but could easily be turned into a reduction from not-all-equal satisfiability. This means that we need gadgets for the wires, AND gates, and OR gates of NCL, where a wire is an arrow that can be turned to point towards either of its ends (colored blue or red), an AND gate must have either its one blue wire or both of its two red wires pointing into it, and an OR gate must have at least one of its three blue wires pointing into it. These can be represented by nonplanar attachments to a planar “substrate” graph with a unique planar embedding whose purpose is to hold the gadgets in place. In the figure below, the substrate is gray and black, the wires are red and blue (as is standard for NCL), and two gates are yellow. The only edges whose contraction could help planarize the graph are the ones with at least one yellow endpoint or exactly one graph endpoint. A wire vertex contracted towards a gate corresponds to an arrow pointing into the gate; it provides more freedom for the adjacent yellow vertex of the gate, which would otherwise have to be contracted into the gray vertex that it shares with the wire. In an OR gate, the freedom provided by an inward-pointing arrow allows the contraction of one yellow-yellow edge, enough to planarize the gate. In an AND gate, it the yellow vertex can be contracted towards the blue wire, towards both red wires, or neither (if all wires point in).
Beyond planarizing matching, it would also be interesting to extend our recognition algorithm to string graphs with higher degrees than three. Is there a polynomial time algorithm for recognizing string graphs with bounded treewidth and bounded degree? Bounded treewidth alone? I don’t know.