Counting Triangulations of Fixed Cardinal Degrees

We consider plane straight-line (PSL) graphs: graphs whose vertices are points in the plane, and whose edges are interior-disjoint segments connecting the vertices at their endpoints. A PSL graph is maximal if adding any edge would result in a graph that is not a PSL graph. Given a PSL graph $G=(V,E)$ and $v\in V$, we write ${\mathrm{deg}}_{𝒩}(v)$ to mean the number of edges incident to $v$ whose other endpoint lies above $v$ in the $y$-direction (“to the north”). The south-, east-, and west-degrees of $v$, written ${\mathrm{deg}}_{𝒮},{\mathrm{deg}}_{ℰ},{\mathrm{deg}}_{𝒲}:V\to \mathbb{N}$ respectively, are defined analogously, and the four are collectively called the cardinal degrees of $G$. We consider only graphs with vertices at distinct $x$- and $y$-coordinates and in general position. We call $\sigma =(V,{\mathrm{deg}}_{𝒩},{\mathrm{deg}}_{𝒮},{\mathrm{deg}}_{ℰ},{\mathrm{deg}}_{𝒲})$ a cardinal signature and call $G$ a realization of $\sigma$ if and only if $G$ is a maximal PSL graph with cardinal signature $\sigma$. Although each graph has a unique cardinal signature, distinct graphs can have the same cardinal signature, even in the restricted setting of maximal PSL graphs; see Figure 1.

We therefore consider the problem of counting realizations of a cardinal degree signature, called #cardinal signature realization, and, in particular, we show this problem is #P-hard. We do so by a reduction from #3-regular bipartite planar vertex cover. However, we first reduce to an intermediary problem, namely, the #tiled noncrossing cycle-set problem, whose input is a tiling: a grid of tiles, where each tile has one of the tile types as in Figure 2, and are arranged to form a collection of red and blue cycles. A solution to this problem is a selection of noncrossing cycles. Figure 3 illustrates the connection between #tiled noncrossing cycle-set and #3-regular bipartite planar vertex cover.

To connect our central problem to #tiled noncrossing cycle-set, we introduce frame graphs. A frame graph $F$ is a grid-like pattern of convex chains of edges, forming roughly square faces called frame cells, corresponding to the tile structure of #tiled noncrossing cycle-set; see the black edges of Figure 4(c). Suppose a roughly horizontal path of $F$ lies just below height $h$. This path is part of the boundary of the subgraph of $F$ whose vertices lie below $h$. The sum of south degrees of all vertices below $h$ tells us how many edges lie entirely in this halfspace. Using Euler’s formula, we confirm that this lower subgraph is maximal PSL, i.e., the edges in this path must be present in every cardinal signature of $F$. Using a left-to-right argument for the nearly vertical paths tells us the realization of the cardinal signature of $F$ is unique. By extension, any graph made by adding edges to $F$ has a cardinal signature whose realizations all have the edges of $F$, i.e., these edges are forced. Thus, we include extra edges to a frame graph to form gadgets, corresponding to tile types; see Figure 4.

We show that a frame graph triangulated by edges chosen from gadgets has a cardinal signature whose realizations are only the ones shown. We first establish our inductive step.

Since having a fixed triangulation to the south and west of a frame cell establishes the triangulation of the frame cell itself, and a consistent choice of light/dark leads to a consistent choice within the cell, we induct on the row and column of a frame cell to show the following.

We bijectively match each solution of a noncrossing tile selection to a realization of a cardinal signature $\sigma$; choosing (not choosing) a tile cycle corresponds to that portion of the triangulation made using light (dark) colored edges. We conclude that the number of cardinal signature realizations of $\sigma$ is the same as the number of noncrossing tile selections of the corresponding cycle-set.