The squaregraphs are planar graphs in which all bounded faces are four-cycles, and each vertex either belongs to the outer face or has degree at least four. The rectangular grids form familiar examples. A grid with \(n\) vertices can have up to \(\lfloor 2n-2\sqrt{n}\rfloor\) edges (depending on how close to square it is) and the same formula can also be obtained for other values of \(n\) by removing vertices from a square or nearly-square grid. For instance, the drawing below is of a partial grid with \(51\) vertices and \(87\) edges, matching the formula as \(87=\lfloor 2\cdot 51-2\sqrt{51}\rfloor.\)

57-vertex 87-edge squaregraph

What about squaregraphs more generally? How many edges can they have? To answer this, I think it’s easier to think about a dual version of the problem. The squaregraphs are exactly the graphs whose vertices represent the cells of a triangle-free weak pseudoline arrangement, and whose edges represent boundaries between cells. Here, a pseudoline is a curve that can be obtained from a line in the plane by a topological deformation of the whole plane, a weak arrangement is a collection of pseudolines such that the intersection of every two pseudolines is either empty or a single crossing point, and it’s triangle-free if no three pseudolines all cross. It’s equivalent to think of these as triangle-free arrangements of lines in the hyperbolic plane, or as triangle-free chord diagrams. The drawing below shows an example; the yellow line segments below are the pseudolines/hyperbolic lines/chords, each blue vertex lies in one of the regions separated by the yellow line segments, and each edge between two blue vertices corresponds to a pair of regions separated by one of the yellow line segments.

A squaregraph and its dual arrangement

If we create this arrangement by adding the dual curves one at a time, then initially we have one vertex and zero edges. Each new line with \(k\) crossings adds \(k+1\) new vertices (by splitting that many regions of the previous arrangement into pairs of regions) and \(2k+1\) new edges (\(k+1\) of them connecting each new region to the one it was split from, and \(k\) of them connecting new regions that are consecutive along the new curve). Therefore, by induction, if there are \(\ell\) lines and \(c\) total crossings, the number of vertices in the squaregraph is \(c+\ell+1\) and the number of edges is \(2c+\ell.\) Therefore, for an \(n\)-vertex squaregraph represented by an arrangement of \(\ell\) lines, the number of edges will fall short of \(2n\) by exactly \(\ell+2.\) To make squaregraphs with a number of edges that is as close to \(2n\) as possible, we need to use as few lines as possible.

But to figure out how few lines we need, we can forget the geometry and fall back to standard graph theory. Consider the intersection graph of the pseudolines. It is a triangle-free graph with \(\ell\) vertices, and Mantel’s theorem tells us that the maximum number of edges in such a graph is \(\lfloor \ell^2/4\rfloor,\) achieved by the complete bipartite graphs. Translating this result back to arrangements, the maximum number of crossings in a triangle-free weak pseudoline arrangement is achieved by partitioning the lines into two equal or nearly-equal sets and making each pseudoline in one set cross each pseudoline in the other set. This is exactly the arrangement that corresponds to a square or nearly-square grid.

We don’t want to maximize crossings for a given number of lines; we want to minimize lines for a given number of squaregraph vertices. But the same result tells us that we can never achieve fewer lines than the grid or partial grid with the same number of vertices, because to do so we would need to use more crossings than are possible for that many lines. Therefore, every \(n\)-vertex squaregraph has at most \(\lfloor 2n-2\sqrt{n}\rfloor\) edges, the number given by the grids and partial grids.

This edge bound turns out to be exactly the same as Swanepoel’s conjectured maximum number of edges in triangle-free penny graphs. The grids and partial grids are penny graphs, and their existence shows that (if true) Swanepoel’s conjectured bound would be tight. But not every squaregraph is a penny graph, and not every triangle-free penny graph is a squaregraph, so the fact that squaregraphs can be proven to obey the same bound doesn’t seem to be helpful in making progress on Swanepoel’s conjecture.