Forbidden patterns in tropical plane curves

A tropical plane curve is a metric graph, G, embedded in \({\mathbb {R}}^2\), which is dual to a regular subdivision \(\varDelta \) of some lattice polygon P. In the smooth case \(\varDelta \) is a unimodular triangulation of P, and the planar graph G is trivalent of genus g, where g agrees with the number of interior lattice points of P. Such graphs have been called tropically planar by  Coles et al. (2019). Here we are concerned with the question: Which graphs G occur in this way?

Known forbidden patterns: graph with a sprawling node (left), a crowded graph (center), and a TIE-fighter graph (right). Each box represents some subgraph of positive genus

Full size image

For any fixed \(g\ge 1\), Castryck and Voight gave a procedure for finding finitely many lattice polygons with exactly g interior lattice points whose triangulations suffice to produce all such graphs (Castryck and Voight 2009). This was employed in Brodsky et al. (2015) and Coles et al. (2019) to computationally determine the tropically planar graphs of genus \(g\le 7\). Despite its success that approach is severely limited by the combinatorial explosion of the number of planar graphs and the number of triangulations of the relevant polygons. While it is doubtful that this can be pushed much further, here we seek to find obstructions for a given trivalent graph to be realizable as a tropical plane curve. It was known previously that graphs with a sprawling node (Cartwright et al. 2016, Proposition 4.1), crowded graphs (Morrison 2020, Lemma 3.5) and TIE-fighter graphs (Coles et al. 2019, Theorem 3.4) cannot occur; cf. Fig. 1. Here we add further forbidden patterns to this list. As an immediate consequence, for the first time, we provide a complete combinatorial characterization of the tropically planar graphs of genus \(g\le 5\), in contrast to the proof in Brodsky et al. (2015) which rests on substantial computer support. More importantly, we identify a particularly interesting “boundary case”: if it is realizable, a graph with a heavy cycle forces a number of geometric restrictions for the polygon P and the triangulation \(\varDelta \). As an example, this leads us to studying a natural family of triangulations, which we call anti-honeycombs. In this way we get a glimpse of tropically planar graphs of genus \(g=8\) and beyond.

While this work is motivated by the desire to understand tropical curves and their moduli, here we concentrate on the combinatorial aspects, which means we do not take edge lengths of metric graphs into account. This comes with the advantage that our results also hold for triangulations which are not regular.

Let \(V\subset {\mathbb {R}}^d\) be a finite set of points. A polytopal subdivision of V is a polytopal complex which covers the convex hull \({{\,\mathrm{conv}\,}}V\) and uses (a subset of) the given point set V as its vertices. If that subdivision is induced by a height function on V, it is called regular. A subdivision which consists of simplices is a triangulation. A comprehensive reference on the subject is the monograph (De Loera et al. 2010) by De Loera, Rambau and Santos. Here we will be concerned with the following case. Let P be a (convex) lattice polygon, i.e., P is the convex hull of finitely many points in \({\mathbb {Z}}^2\), and \(V=P\cap {\mathbb {Z}}^2\) is the set of lattice points in P. A triangulation \(\varDelta \) of V is unimodular if each triangle in \(\varDelta \) has normalized area one, i.e., Euclidean area \(\tfrac{1}{2}\). This is the case if and only if \(\varDelta \) uses all points in V. We write \(\partial P\) for the boundary of P and \({{\,\mathrm{int}\,}}P\) for its interior. The number \(g(P)=\#({{\,\mathrm{int}\,}}P)\) of interior lattice points is the genus of P; cf. Figure 2 for an example.

Anti-honeycomb triangulation \(\varDelta _{(-2,4;-2,4;-2,4)}\) of genus 4 (left), its dual graph (center), and the corresponding skeleton (right)

Full size image

Let \(\varDelta \) be a (not necessarily unimodular) triangulation of V. The dual graph \(\varGamma =\varGamma (\varDelta )\) is the abstract graph whose nodes are the triangles of \(\varDelta \); they form an edge in \(\varGamma \) if two triangles share an edge in \(\varDelta \). The dual graph is necessarily connected and planar, and each node has degree at most three.

Next we describe a procedure to obtain a certain graph minor of \(\varGamma \). First, if there is a node of degree one, we delete it together with the unique incident edge. We repeat this step until no nodes of degree one are left. The remaining edges are nonredundant. Second, if there is a node of degree two, we delete the node and join its neighbors by an edge. Again we repeat until there are no more nodes of degree two. The resulting graph is the skeleton, which we denote \(G=G(\varDelta )\). By construction the skeleton is a trivalent planar graph, and it does not depend on the ordering in which the edge deletions and contractions are performed (Gordon and McNulty 2012, Section 3.1.2). In this way each edge of G arises as an edge path in \(\varGamma \). This yields a surjective map, which we denote \(\eta \), from the nonredundant edges of \(\varGamma \) onto the edges of G. Note that this contraction map \(\eta \) is undefined for any edge which is redundant. This elementary description of the skeleton is algorithmic in nature and serves our purposes.

A split is a subdivision of V with exactly two maximal cells; it is necessarily regular (Herrmann and Joswig 2008, Lemma 3.5). If U and W are the two maximal cells of a split, then the intersection \(U\cap W\) is a common edge of the two convex polygons U and W. It spans the corresponding split line. A set of splits of V is weakly compatible if there is a triangulation which simultaneously refines them all. Moreover, a set of splits is (strongly) compatible if any two split lines do not meet in the interior of P. Compatibility implies weak compatibility. The split lines of two weakly compatible splits which are not strongly compatible must meet in a point in V, i.e., an interior lattice point of P. An edge e of the connected graph G is a cut edge if deleting e creates two connected components. Otherwise e lies in some cycle of G.

The following three technical results are extracted from the proof of (Coles et al. 2019, Theorem 3.4), where cut edges are called “bridges”.

Lemma 1

Let e be a cut edge of G. Then \(\eta ^{-1}(e)\) comprises a single cut edge of \(\varGamma \), which is dual to an edge, s, of \(\varDelta \). Moreover, the vertices of s lie on the boundary \(\partial P\), and s spans a split line of V.

Here the “vertices” are the two endpoints of the edge s. In the unimodular case these are also the only lattice points contained in s. Our arguments below do not rely on the uniqueness of the cut edge in \(\eta ^{-1}(e)\). It suffices to know that such edge (and its dual edge s) exist.

Lemma 2

Let e be an edge between \(v_{1}\) and \(v_{2}\) in a cycle, C of G. Furthermore, let \(T_1\) and \(T_2\) be triangles in \(\varDelta \) which correspond to \(v_{1}\) and \(v_{2}\) on the path \(\eta ^{-1}(e)\). Then \(T_1\) and \(T_2\) share an interior lattice point of P, and this is dual to C.

Lemma 3

Let \(z\in V\) be some lattice point in P with two incident triangles \(T_1={{\,\mathrm{conv}\,}}\{z,a_1,b_1\}\) and \(T_2={{\,\mathrm{conv}\,}}\{z,a_2,b_2\}\) both of which are in \(\varDelta \). Further, let \(L_i\) be the line spanned by \(a_i\) and \(b_i\), for \(i=1,2\). Suppose that \(L_1\) and \(L_2\) meet in some point, say w, such that \(a_i\) is closer to w than \(b_i\), for \(i=1,2\). Then the interior of the quadrangle \({{\,\mathrm{conv}\,}}\{z,a_1,w,a_2\}\) does not contain a point in V, unless \(a_1=a_2=w\).

With this we can take a small first step to our main results. Recall that Lemma 1 associates a split of V to each cut edge of G.

Lemma 4

Splits corresponding to distinct cut edges are compatible.

Proof

It suffices to consider pairs of splits. From Lemma 1 the cut edges \(e_1\) and \(e_2\) yields two split lines, \(S_1\) and \(S_2\), which may not be unique. Unless \(S_1\) and \(S_2\) are compatible, they must meet in a point of the point configuration V, which does not lie on \(\partial P\), i.e., an interior lattice point of P. Yet, by Lemma 1 the line \(S_1\) (and similarly \(S_2\)) contains precisely two points of V, and neither lies in the interior. \(\square \)

The connection to tropical geometry comes about as follows. See the book by Maclagan and Sturmfels (2015) for the general context and Brodsky et al. (2015) for a detailed analysis of the case which is of interest here. Let \(\varPhi \) be a bivariate tropical polynomial. Its vanishing locus, the tropical hypersurface \({\mathcal {T}}={\mathcal {T}}(\varPhi )\), is a tropical plane curve in \({\mathbb {R}}^2\). The Newton polygon of \(\varPhi \) is a lattice polygon, and the terms of \(\varPhi \) correspond to lattice points in P. Moreover, the coefficients of \(\varPhi \) induce a regular subdivision, \(\varDelta \), on those lattice points which are dual to \({\mathcal {T}}\), i.e., \({\mathcal {T}}\) essentially agrees with \(\varGamma (\varDelta )\). The tropical plane curve \({\mathcal {T}}\) is smooth if its dual subdivision \(\varDelta \) is unimodular. Conversely, each unimodular regular triangulation of P arises in this way. In that case the edges of G (with their lengths, which we do not need here) describe \({\mathcal {T}}\) as a point in the moduli space \({\mathbb {M}}_g^{\text {planar}}\) of tropical plane curves of genus g. Skeleta of unimodular regular triangulations of lattice polygons are tropically planar or “troplanar” graphs in Coles et al. (2019).

Example 1

We consider the anti-honeycomb triangle

which occurs as \(Q_3^{(4)}\) in Brodsky et al. (2015). The genus is \(g(A_{(-2,4;-2,4;-2,4)})=4\). We call the unimodular triangulation \(\varDelta _{(-2,4;-2,4;-2,4)}\), shown in Fig. 2 (left), the anti-honeycomb triangulation of \(A_{(-2,4;-2,4;-2,4)}\). Its skeleton, shown in Fig. 2 (right) and called (303) in Brodsky et al. (2015), features three cut edges which correspond to three compatible splits of \(A_{(-2,4;-2,4;-2,4)}\). The triangulation \(\varDelta _{(-2,4;-2,4;-2,4)}\) is regular, whence it defines a moduli cone of tropical plane curves. That cone is 7-dimensional, while the entire moduli space \({\mathbb {M}}_4^{\text {planar}}\) has dimension nine; see Brodsky et al. (2015, Table 4). See Sect. 5 for a more comprehensive discussion of anti-honeycomb polygons, their triangulations and the notation (1).

We now sketch the forbidden patterns which are known already. A node in G is sprawling if its deletion leaves three connected components; cf. Fig. 1 (left). This obstruction to tropical planarity was identified in Cartwright et al. (2016, Proposition 4.1) and Brodsky et al. (2015, Proposition 8.3). Note that graphs with a sprawling node were called “sprawling” in Brodsky et al. (2015) and Coles et al. (2019). A planar embedding of a graph G is called crowded if either: there exist two bounded regions sharing at least two edges; or, there exists a bounded region sharing an edge with itself. If all planar embeddings of G are crowded, then G itself is said to be crowded. In Morrison (2020, Lemma 3.5), it is shown that crowded graphs can never be tropically planar. Additionally, Morrison (2020, Corollary 3.7) describes a family of crowded graphs, and this is depicted in Fig. 1 (center). A graph is a TIE-fighter if it looks like the one in Fig. 1 (right). TIE-fighter graphs can never be tropically planar; this was shown in (Coles et al. 2019, Theorem 3.4).

Let P be a lattice polygon with precisely g interior lattice points. Moreover, let \(\varDelta \) be a unimodular triangulation of P with dual graph \(\varGamma =\varGamma (\varDelta )\) and skeleton \(G(\varDelta )=G\). The contraction map \(\eta \) sends nonredundant edges of \(\varGamma \) to edges of G. The g interior lattice points of P bijectively correspond to the bounded regions of the planar graph G. By Euler’s formula we have \(g = m - n + 1\), where m and n are the numbers of edges and nodes of G, respectively. Our arguments in this section do not require \(\varDelta \) to be regular. That is, our results extend to a class of planar graphs, which is slightly more general than tropical plane curves.

Two lattice polygons, P and Q, are unimodularly equivalent if there is a lattice vector \(\alpha \in {\mathbb {Z}}^2\) and an integer linear transformation \(\tau \in {{\,\mathrm{SL}\,}}(2,{\mathbb {Z}})\) such that \(P=\alpha +\tau (Q)\); cf. (De Loera et al. 2010, Section 9.3). In that case, we have \(P\cap {\mathbb {Z}}^2=\alpha +\tau (Q\cap {\mathbb {Z}}^2)\), i.e., the lattice points are transformed alike. The map \(x\mapsto \alpha +\tau (x)\) is a unimodular transformation.

Lemma 5

Assume that P contains a unimodular triangle with vertices a, b, z such that neither a nor b is a vertex of P, and z is an interior lattice point. If a and b lie on \(\partial P\) then either a and b lie on a common edge of P or the lattice point \(a+b-z\) is contained in P.

Proof

Up to unimodular equivalence we may assume \(a=(1,0)\), \(b=(0,1)\) and \(z=(0,0)\). Let L and M be the lines spanned by the edges of P containing a and b, respectively. Suppose that (1, 1) is not contained in P. Since P is a lattice polygon, then the intersection of P with the positive orthant agrees with the unit triangle abz. This entails that L and M agree, which means that \(L=M\) defines an edge of P, and this contains a as well as b. \(\square \)

Graph with the heavy cycle C

Full size image

Definition 1

We say that a cycle C in a planar graph G is heavy, if

1. (i)

   it has two nodes, \(v_1\) and \(v_2\), such that \(v_i\) is incident with a cut edge \(e_i\) connecting \(v_i\) with a subgraph \(G_i\) of positive genus;

2. (ii)

   and there is a third subgraph, \(G_3\), also of positive genus, which shares at least one node with the cycle C; cf. Fig. 3.

In particular, a graph with a heavy cycle has genus at least four. From the classification of hyperelliptic graphs in Morrison (2020), we infer that a graph with a heavy cycle is not hyperelliptic. Moreover, it follows from Lemma 1 that there are split lines, \(S_1\) and \(S_2\), dual to the edges \(e_1\) and \(e_2\) of G. While the split lines may not be unique we just pick some. By Lemma 4 the splits \(S_1\) and \(S_2\) are compatible, and thus P decomposes into a union of three lattice polygons \(P_1\), \(P_2\) and \(P'\) such that \(\varDelta \) induces triangulations of all three. In this way, we get triangulations \(\varDelta _1\), \(\varDelta _2\) and \(\varDelta '\) such that the component \(G_i\) is the skeleton of \(\varDelta _i\) for \(i=1,2\), and \(G_3\cup C\) is the skeleton of \(\varDelta '\). The triangles in \(\varDelta '\) which are dual to \(v_1\) and \(v_2\) are denoted \(T_1\) and \(T_2\), respectively. We refer to the polygon \(P'\) as the heavy component of P, and likewise \(\varDelta '\) is the heavy component of \(\varDelta \). Expressed in the language of Coles et al. (2019), the heavy component \(\varDelta '\) arises from \(\varDelta \) via “bridge-reduction”.

The following lemma is the technical core of this paper. Its proof is a bit cumbersome, with several cases to distinguish. However, it is rather powerful as it delineates a fine border between trivalent planar graphs which are realizable as skeleta of tropically planar curves and those which are not.

Lemma 6

Suppose that G has a heavy cycle with cut edges \(e_1\) and \(e_2\) as in Fig. 3. Then the triangles \(T_1\) and \(T_2\) in \(\varDelta \) share an edge [z, w], where z is the interior lattice point dual to C, and the split lines \(S_1\) and \(S_2\) intersect in w, which is a vertex of \(P'\), and which lies in the boundary of P.

Before we enter the proof, we sketch an outline. The overall strategy is indirect, i.e., we will assume that \(T_{1}\) and \(T_{2}\) share a vertex but not an edge. Now the split lines from Lemma 4 are either parallel or not; cf. Fig. 4. In both cases we can exploit the convexity of the four lattice polygons \(P_1\), \(P_2\), \(P'\) and P to arrive at contradictions. The situation with intersecting split lines is the more difficult one, as it ramifies into sub-cases.

Proof

By Lemma 2 the triangles \(T_1\) and \(T_2\) share a vertex z, which is the interior lattice point in P dual to the heavy cycle C. Up to a unimodular transformation we may assume that \(z = (0,0)\), and \(T_1={{\,\mathrm{conv}\,}}\{z,(1,0),(0,1)\}\).

We consider the point (1, 1). We notice that if \((1,1) \not \in P\), then by convexity of P, the positive genus component attached to the split edge \(s_{1} = [(1,0),(0,1)]\) is squeezed between the lines \(y= 0\) and \(y=1\), which has no interior lattice points and we get a contradiction. Therefore the point (1, 1) lies in P. We want to show that (1, 1) is an interior lattice point of \(P_1\) (and P). First, since (1, 0) is in the boundary and z is in the interior of P, there are no interior lattice points on the ray \((1,0)+{{\,\mathrm{pos}\,}}\{(1,0)\}\). Similarly, there are no interior lattice points on \((0,1)+{{\,\mathrm{pos}\,}}\{(0,1)\}\). However, since \(G_1\) has positive genus at least one interior lattice point of \(P_1\) exists, and it must lie in the translated orthant \((1,1)+{{\,\mathrm{pos}\,}}\{(1,0),(0,1)\}\). As (1, 0) and (0, 1) lie in \(P_1\) it follows from the convexity of \(P_1\) that (1, 1) must be an interior lattice point. Now consider the triangle \(T_2={{\,\mathrm{conv}\,}}\{z,(\alpha ,\beta ),(\gamma ,\delta )\}\) where \(\alpha ,\beta ,\gamma ,\delta \in {\mathbb {Z}}\) with

Suppose \(T_1\) and \(T_2\) do not share an edge. We are aiming for a contradiction, which then establishes a proof of this lemma. Since \((1,1)\in {{\,\mathrm{int}\,}}P_1\) the horizontal line \((0,1)+{\mathbb {R}}(1,0)\) intersects \(P'\) only in (0, 1). Similarly, the vertical line \((1,0)+{\mathbb {R}}(0,1)\) intersects \(P'\) only in (1, 0). As \((\alpha ,\beta )\), \((\gamma ,\delta )\), (1, 0), and (0, 1) are pairwise distinct this yields \(\alpha ,\beta ,\gamma ,\delta \le 0\).

First, suppose the split line \(S_2\) is parallel to \(S_1\). As \(T_2\) is a unimodular triangle \(S_2\) is the line through \((-1,0)\) and \((0,-1)\). Then, \(S_{2}\) and \(\alpha ,\beta ,\gamma ,\delta \le 0\) forces \(\alpha =\delta =-1\) and \(\beta =\gamma =0\).

Two possibilities for \(S_{1}\) and \(S_{2}\), which are ruled out a posteriori in the proof of Lemma 6. Left: \(S_{1}\) and \(S_{2}\) are parallel. Right: \(S_{1}\) and \(S_{2}\) intersect in a point

Full size image

We consider the lattice points \(q=(-1,1)\) and \(r=(1,-1)\). As \(P'\) has positive genus, it follows from Lemma 5 that either q or r is an interior lattice point of \(P'\). By symmetry we may assume \(r\in {{\,\mathrm{int}\,}}P'\). Then, the point q can either lie on the boundary of P or is not in P. Now the interval \([(1,1),(1,-1)]\) is the convex hull of two interior lattice points of P, but it contains the boundary point \(p_1\) in its relative interior. Hence we obtain a contradiction.

We conclude that the split lines \(S_1\) and \(S_2\) intersect in some point \(w=(\psi ,\omega )\), as depicted in the Fig. 4. Since \(T_{1}\) is fixed, \(T_{1}\) and \(T_{2}\) do not share an edge and \(\alpha , \beta , \gamma , \delta \le 0\), we obtain \(\omega \le 0\). We use the labels from Fig. 4 and intend to show that w lies in \(\partial P\). Suppose the contrary. Then, due to Lemma 4, the point w must lie outside P. The three points \(p_1:=(1,0)\), w and (0, 1) are collinear with \(p_1\) in the middle; hence w is closer to \(p_1\) than to (0, 1) with respect to Euclidean distance. From (2) it follows that w is closer to \(p_2:=(\gamma ,\delta )\) than to \((\alpha ,\beta )\). Applying Lemma 3 we infer that the interior of the quadrangle \({{\,\mathrm{conv}\,}}\{z,p_1,w,p_2\}\) does not contain an interior lattice point of P. We realize that since the triangles \(T_{1}\) and \(T_{2}\) do not share an edge, and since \(p_1,p_2\in \partial P\) therefore in this case \([p_1,p_2]\) is a boundary edge and the triangle \({{\,\mathrm{conv}\,}}\{z,p_{1},p_{2}\}\) belongs to \(\varDelta \).

We now look at possible coordinates of the point \(p_{2}=(\gamma ,\delta )\). Since the triangle \({{\,\mathrm{conv}\,}}\{z,p_1,p_2\}\) is unimodular and as \(\delta \le 0\) we have \(\delta =-1\). Hence \(p_{2}\) lies on the ray \(\{(\gamma , \delta ) :\gamma \le 0, \delta = -1\}\). We consider some values of \(\gamma \) starting with the case of \(\gamma = 0\). Then (2) implies that \((\alpha ,\beta )\) is on the line \(x=-1\), i.e., \(\alpha = -1\). We explore the possible values for \(\beta \).

For \(\beta =-2\) the split edge on the line \(S_2\) would be \(s_{2}=[(0,-1),(-1,-2)]\). This cannot be as then \(S_2\) would contain \(p_1\) as a third boundary point, a contradiction to Lemma 1. For \(\beta =-1\) and \(s_{2}=[(0,-1),(-1,-1)]\), we realize that the polygon \(P_{2}\) is bounded in the rectangular strip between the parallel lines \(y=x\) and \(y=x-1\). Yet there is no interior lattice point between them, and this contradicts \(G_2\) to have positive genus. Any other value of \(\beta < -2\) contradicts the convexity of P at z. This rules out the possibility \(\gamma =0\).

The arguments for excluding the other values of \(\gamma \) are very similar. We summarize them briefly. For \(\gamma = -1\) we obtain \(\beta = \alpha + 1\). Then either \(s_{2}=[(-1,-1),(-1,0)]\), and we obtain \(\omega = 2 \ge 0\), which is absurd. Or \(s_{2}=[(-1,-1),(-2,-1)]\), whence \(P_2\) is squeezed between the lines \(2y=x\) and \(2y=x-1\), which does not leave space for an interior lattice point. Or \(s_{2}=[(-1,-1),(-3,-2)]\), which then lies on the line spanned by the boundary edge \([p_{1},p_{2}]\). Again, any other value of \(\beta \) on the line \(y = x + 1\), contradicts the convexity of P at z.

Similarly, \(\gamma = -2\) implies \(2\beta = \alpha +1\). Then either \(s_{2}=[(-2,-1),(-1,0)]\), and we obtain \(\omega = 1 \ge 0\), which is absurd. Or \(s_{2}=[(-2,-1),(-3,-1)]\), whence \(P_2\) is squeezed between the lines \(3y=x\) and \(3y=x-1\), which does not leave space for an interior lattice point. Or \(s_{2}=[(-2,-1),(-5,-2)]\), which then lies on the line spanned by the boundary edge \([p_{1},p_{2}]\). Again, any other value of \(\beta \) on the line \(2y = x + 1\), contradicts the convexity of P at z.

The case \(\gamma \le -3\) is left. Then the point \((\alpha ,\beta )\) lies on the line \(-\gamma y = x + 1\). The following three possibilities occur for the split edge \(s_{2}\). Either \(s_{2} = [(-1,0),(\gamma ,-1)]\), and we obtain \(\omega \ge 0\), forcing \(\omega =0\). In this case we see that there is no edge to join between the points \((-1,0)\) and (0, 1) such that the polygon P remains convex, which gives us a contradiction. Or \(s_{2} = [(\gamma -1,-1)(\gamma ,-1)]\), whence \(P_2\) is squeezed between the lines \((1-\gamma )y=x\) and \((1-\gamma )y=x-1\), which does not leave space for an interior lattice point. Or \(s_{2}=[(2\gamma -1,-2),(\gamma ,-1)]\), which then lies on the line spanned by the boundary edge \([p_{1},p_{2}]\). Any other value of \(\beta \) on the line \(-\gamma y = x + 1\), contradicts the convexity of P at z.

Therefore, finally, we conclude that there is no lattice point \(p_{2} = (\gamma , \delta )\) such that the triangle \({{\,\mathrm{conv}\,}}\{z,p_{1},p_{2}\}\) belongs to \(\varDelta \). Hence, our initial assumption was wrong, and the triangles \(T_{1}\) and \(T_{2}\) do share the edge [z, w], where \(w=p_1=p_2\) is the intersection of \(S_1\) and \(S_2\). Consequently, \(s_1\) and \(s_2\) are two distinct edges of \(P'\), and so w is a vertex of \(P'\). \(\square \)

A graph with a sprawling triangle; \(e_{1}\), \(e_{2}\), \(e_{3}\) are cut edges; \(G_1\), \(G_2\), \(G_3\) are subgraphs of positive genus

Full size image

We notice that the anti-honeycomb triangulation of genus 4 in Example 1 and Fig. 2 is a positive example for the result in Lemma 6. For the three triangular cells containing the split edges and sharing a common vertex, each pair of them has a common edge. In fact, the specific shape of the heavy component in that example gives rise to another concept, which covers a special case of Definition 1.

Definition 2

We say that the planar graph G has a sprawling triangle if it has a cycle with three nodes, each of which is also incident with a unique cut edge, such that at the other end there is a subgraph of positive genus; cf. Fig. 5.

It turns out that Example 1 is the only case where this occurs:

Theorem 1

If G has a sprawling triangle then \(g=4\), and, up to unimodular equivalence, we have

Proof

We use the notation from Fig. 5. Let \(s_{1},s_{2}\) and \(s_{3}\) be the split edges in \(\varDelta \) corresponding to the cut edges \(e_{1}, e_{2}\) and \(e_{3}\). Using Lemma 6 on these three splits, we obtain that each pair of them intersects in a point on \(\partial P\). This gives three lattice points a, b, c in the boundary of P such that each pair is joint by one of the three edges \(s_1,s_2,s_3\). Let \(\varDelta |_{abc}\) be the subcomplex of \(\varDelta \) restricted to the lattice triangle abc. Its skeleton is the sprawling triangle, whose genus is one. Hence there is a unique interior lattice point, z, of P contained in abc. It follows that the lattice triangle abc has normalized area three, and its unimodular triangulation into abz, acz, and bcz forms the induced subcomplex \(\varDelta |_{abc}\). Those maximal cells of \(\varDelta \) are dual to the three nodes of the sprawling triangle of G.

As in the proof of Lemma 5 we may assume that \(a=(1,0)\), \(b=(0,1)\) and \(z=(0,0)\). It then follows that \(c=(-1,-1)\). Directly from Definition 2 it follows that the line ab is dual to a cut edge in G and thus induces a split of \(\varDelta \). All the interior lattice points corresponding to a region of the subgraph \(G_1\) must lie in the halfspace defined by ab which does not contain z. Since z is the only interior lattice point of P which does not correspond to a region of \(G_1\cup G_2\cup G_3\), the lattice points a, b and c must lie in the boundary of P.

Now Definition 2 requires the subgraphs \(G_1\), \(G_2\) and \(G_3\) to have positive genus. This excludes the possibility that one of the three points a, b, c is a vertex of P. Thus they must lie on pairwise distinct edges of P. Now we can apply Lemma 5 three times to learn that the three lattice points

are contained in P.

Let L, M, N be the three lines spanned by the edges of P through a, b, c, respectively. Suppose that (1, 1) is a boundary point of P. Then, since P is lattice polygon, (1, 1) is the intersection point of L and M and thus a vertex of P. This contradicts the fact that \(G_1\) has positive genus, and it follows that (1, 1) is an interior lattice point of P. By symmetry, also \((0,-1)\) and \((-1,0)\) are interior lattice points of P.

Now the lattice point (1, 2) is not contained in P because it would then need to lie on the line M, together with \((-1,0)\). But this cannot happen as \((-1,0)\) was already identified as an interior point of P. Similarly, (2, 1) is not contained in P either. Yet this implies that the intersection of the lines L and M lies strictly between the two parallel lines \((1,0)+\lambda (1,1)\) and \((0,1)+\lambda (1,1)\). Thus there is at least one vertex of P, which must be a lattice point, on the line \((0,0)+\lambda (1,1)\). This forces (2, 2) to lie in P.

Again the situation is symmetric, which is why also \((-2,0)\) and \((0,-2)\) lie in P. The single choice left is that (2, 2) as well as \((-2,0)\) and \((0,-2)\) are vertices of P, and L, M, N are the only facets. This establishes \(P = {{\,\mathrm{conv}\,}}\{(-2,0),(0,-2),(2,2)\}\). The claim about \(\varDelta \) follows as there is only one way to extend the triangulation from the triangle abc to all of P. \(\square \)

Remark 1

Contracting a sprawling triangle in a planar graph yields a graph with a sprawling node, and this cannot be tropically planar. Therefore, Example 1 shows that the class of tropically planar graphs is not minor closed; this was observed before (Coles et al. 2019, Figure 6).

Graphs with a sprawling triangle form special cases of graphs with a heavy cycle. Thus our main technical result, Lemma 6, allowed us to derive decisive structural constraints for triangulations whose skeleton has a sprawling triangle in Theorem 1. Now we are looking into another special class of groups with a heavy cycle, aiming for a second structural result on unimodular triangulations of lattice polygons.

Definition 3

We say that a connected trivalent planar graph G has a heavy cycle with two loops if it has the form as described in Fig. 6, where the shaded region represents a subgraph of positive genus.

Heavy cycle with two loops

Full size image

The latter is the special case of Definition 1, where \(g(G_1)=1=g(G_2)\). This type of skeleton does actually occur.

Example 2

The quadrangle \(Q_4^{(5)}\) of genus 5, cf. (Brodsky et al. 2015, Figure 22), admits a (regular) unimodular triangulation whose skeleton features a heavy cycle with two loops, cf. (Brodsky et al. 2015, Figure 23).

Our aim in this section is to establish the following,

Theorem 2

Suppose G is a graph with a heavy cycle C and two loops with cut edges, \(e_{1}\) and \(e_{2}\), as in Fig. 6. Then the heavy component \(P'\) can have at most three interior lattice points, and these lie on the line spanned by the edge \([z,w] \in \varDelta \), where z is the interior lattice point dual to C, and w is the intersection point of the split edges \(s_{1}\) and \(s_{2}\). In particular, \(P'\) is hyperelliptic and \(g\le 5\).

Proof

It follows from Lemma 6 that the two triangles share the edge [z, w], where \(w\in \partial P\) is the point where the two split edges meet. We will first show that the interior lattice points of \(P'\) lie on the line spanned by [z, w].

This illustrates Theorem 2: general sketch (left) and the case when \(g(P') \ge 4\) (right), which is impossible

Full size image

As previously, we fix \(T_{1} = {{\,\mathrm{conv}\,}}\{(0,0),(0,1),(1,0)\}\) and use the labels from Figure 7; in particular, we may assume that \(w=(0,1)\). Using Lemma 6 and the unimodularity of \(T_{2}\), we realize that \(p_{2}\) must lie on the line \(x=-1\); so let \(p_{2}=(-1,-k)\) for some integer k. We use Lemma 5 on the points \(z=(0,0)\), \(w=(0,1)\) and \(p_{1}=(1,0)\) and infer that the point \(r:=(1,1)\) is an interior lattice point of P; moreover it is the unique interior lattice point of \(P_{1}\). Similarly, we infer that the point \(r':=(-1,-k+1)\) is the unique interior lattice point of \(P_{2}\). By considering the lines connecting the interior point r with the boundary points \(p_1\) and w, respectively, we see that \(k\ge 0\). The same argument shows that the entire polygon \(P'\) is squeezed between the lines \(x=1\) and \(x=-1\). In particular, the interior lattice points of \(P'\) lie on \(x=0\), which is the line spanned by z and w.

Next we will show that \(g(P')\le 3\). We assume the contrary, i.e., \(g(P')\ge 4\) Then, since all interior lattice points of \(P'\) lie on the line \(x=0\), the point \((0,-3)\) must be an interior lattice point of P.

The vertical line \(x=1\) contains the point \(p_1\), which is a boundary point, and r, which is an interior lattice point. It follows that there is a lattice point \((1,\lambda )\) in the boundary of \(P_1\) for \(\lambda >1\); in particular, either \((1,2)\in P_1\) or the boundary edge at w passes through a point in the open interval ((1, 2), (1, 1)). Also, as \((0,-3)\) is an interior point, no point in \(\partial P_{1}\) is present on the line \(y=3x-3\). We realize that in this case \(P_{1}\) is contained in the triangle \({{\,\mathrm{conv}\,}}\{p_1,w,(1,3)\}\). However, this triangle has no valid lattice point which could be a vertex of \(P_{1}\); recall that (1, 3) has been excluded; see Fig. 7. This provides the desired contradiction, and thus \(g(P') \le 3\). \(\square \)

The above result is sharp as Example 2 shows. The following summarizes the known obstructions to tropical planarity together with our new results.

Theorem 3

A trivalent planar graph of genus \(g\ge 3\) is not tropically planar if one of the following holds:

1. (i)

   it contains a sprawling node, or

2. (ii)

   it contains a sprawling triangle and \(g\ge 5\), or

3. (iii)

   it is crowded, or

4. (iv)

   it is a TIE-fighter, or

5. (v)

   it has a heavy cycle with two loops such that the interior lattice points of the heavy component do not align with the intersection of the two split lines.

Examples of non realizable graphs of genus 7 and 8

Full size image

For instance, the preceding result excludes the graphs in Fig. 8.

The purpose of this section is to define a class of lattice polygons each of which admits a special triangulation. This is motivated by Theorem 1, which characterizes one of these triangulations. We believe that the entire family deserves some attention. Consider three families of parallel lines:

where \(k,\ell ,m\in {\mathbb {Z}}\). By picking a sixtuple \(\pi =(k,k';\ell ,\ell ';m,m')\), with \(k<k'\), \(\ell <\ell '\), and \(m<m'\) we obtain a polygon \(A_\pi \) which is defined by three pairs of inequalities, where each pair comes from one of the parallel families (3). We call \(A_\pi \) the anti-honeycomb polygon of type \(\pi \); in general, this is not a lattice polygon. The following characterizes when the lines from the three families intersect at lattice points; we omit the proof, which is a direct calculation.

Lemma 7

We have

1. (i)

   \(L_k \wedge M_\ell \in {\mathbb {Z}}^2\) if and only if \(k-\ell \) is divisible by 3;

2. (ii)

   \(L_k \wedge N_m \in {\mathbb {Z}}^2\) if and only if \(k-m\) is divisible by 3;

3. (iii)

   \(M_\ell \wedge N_m \in {\mathbb {Z}}^2\) if and only if \(\ell -m\) is divisible by 3.

The name comes about from the connection to the “honeycomb polygons” studied in Brodsky et al. (2015, pp. 10ff). Note that not all of the six inequalities need to be facet defining, whence \(A_\pi \) is a hexagon, a pentagon, a quadrangle or a triangle. For instance,

is a triangle, and its genus equals

We fix a type \(\pi =(k,k';\ell ,\ell ';m,m')\), and we let \(V=A_{\pi }\cap {\mathbb {Z}}^2\) be the set of lattice points in \(A_\pi \). Intersecting with the shifted lattice

of index 3 we obtain a subset \(V'=V\cap {\mathcal {L}}\) of the lattice points in \(A_\pi \). The families of lines (3) yield weakly compatible splits of the point configuration \(V'\), and they induce a triangulation \(\varDelta _\pi '\) of the lattice points in \(V'\). Notice that all the points in \(V \setminus V'\) lie in the interior \({{\,\mathrm{int}\,}}A_{\pi }\). Since none of these lattice points lies on any of the lines (3) it follows that each of them is contained in the interior of a unique triangle of \(\varDelta _\pi '\). Employing stellar subdivisions at the points in \(V \setminus V'\) this yields a triangulation \(\varDelta _\pi \) of V, which we call the anti-honeycomb triangulation of type \(\pi \). Figure 2, Example 1, and Theorem 1 are concerned with the case \(\pi =(-2,4;-2,4;-2,4)\) of genus 4. Figure 9 shows a genus 19 anti-honeycomb triangulation along with its corresponding skeleton for \(\pi =(4,-8;4,-8;4,-8)\).

Anti-honeycomb triangulation of genus 19 on the left, and the corresponding skeleton on the right

Full size image

The honeycomb curves yield moduli cones of maximal dimension \(2g+1\), where g is the genus, cf. (Brodsky et al. 2015, Theorem 1). In contrast the anti-honeycomb curves form a large family whose moduli cones are much smaller. For instance, a direct polymake (Gawrilow and polymake 2000) computation shows that the moduli cone of \(\varDelta _{(4,-8;4,-8;4,-8)}\) is only 28-dimensional, whereas the upper bound \(2g+1\) equals 39.

Example 3

Two interesting classes of anti-honeycomb quadrangles are:

They arise from the triangle \(A_{(k,-2k;k,-2k;k,-2k)}\) in (4) by imposing \(M_{k-3}\) and \(L_{3-2k}\), respectively, as additional facets. The quadrangle \(A_{(k,-2k;k,k-3;k,-2k)}\) is a lattice trapezoid of genus \(2k-1\), while \(A_{(k,3-2k;k,k-3;k,-2k)}\) is a lattice parallelogram of genus \(2k-2\). These examples provide anti-honeycomb polygons of arbitrary genus. Additionally, their skeleta are hyperelliptic, despite the fact that the interior lattice points do not lie on a line. The first few cases are shown in Fig. 10. Because of their shapes we call them anti-honeycomb quadrangles of zigzag type.

Anti-honeycomb quadrangles of zigzag type and their skeleta; genus 3, 4 and 5

Full size image

The anti-honeycomb polygons of low genus can be found by directly inspecting the possibilities of stacking copies of the elliptic “building block” \(A_{(1,-2;1,-2,1,-2)}\).

Proposition 1

The anti-honeycomb polygons of genus \(g \le 6\) are unimodularly equivalent to quadrangles of zigzag type or to the triangle \(A_{(2,-4;2,-4;2,-4)}\).

Up to an affine transformation, which is not a lattice transformation, the three families of lines in (3) form a Coxeter hyperplane arrangement of type \(\tilde{A}_2\). This generalizes to arbitrary dimensions, and so does the construction of the anti-honeycomb triangulations. The resulting anti-honeycomb polytopes are affine images of the “alcoved polytopes” of  Lam and Postnikov (2007). Further details will be explored elsewhere.

The classification of the tropically planar graphs of genus \(g\le 5\) was obtained in Brodsky et al. (2015). Theorem  3 now allows for a combinatorial characterization:

Corollary 1

A trivalent planar graph of genus \(g\le 5\) is tropically planar if and only if none of the obstructions in Theorem 3 occurs.

Proof

The trivalent graphs of low genus have been classified in Balaban (1976). For \(g=3\) there are five such graphs, one of which has a sprawling node; the other four are tropically planar (Brodsky et al. 2015, Theorem 5.1.) For \(g=4\) there are 17 graphs: one is non-planar, three have a sprawling node, the remaining 13 are tropically planar (Brodsky et al. 2015, Theorem 7.1). This was known before.

There are exactly 71 trivalent graphs of genus 5. Among them only 52 are planar without a sprawling node (Brodsky et al. 2015). Of these 14 were ruled out by explicit computations (Brodsky et al. 2015), which leaves 38 tropically planar graphs of genus 5. One of the key contributions of Coles et al. (2019), Figure 8 is to obtain obstructions to tropical planarity, which rules out another ten, which are crowded or TIE-fighters.

The four genus 5 graphs that are not ruled out by any prior known criteria

Full size image

The eight trivalent planar graphs of genus 6, which are not tropically planar (Coles et al. 2019), but which are not covered by Theorem 3

Full size image

As our new contribution we can now discuss the remaining four graphs, which are shown in Fig. 11. Firstly, we observe that all of these exhibit a heavy cycle. The graph labeled “a” has a heavy cycle with two loops, but the component away from the two loops is not hyperelliptic; i.e., it is ruled out by Theorem 2. The second graph, labeled “b” also has a heavy cycle with two loops, the component (of genus 3) away from the two loops is even hyperelliptic. However, we see that the interior point z dual to the heavy cycle would lie in between the other two interior lattice points in the hyperelliptic polygon dual to the genus 3 component; the latter contradicts Theorem 2, which says that the interior lattice points in the genus 3 component should lie below z on the line spanned by z and w, where w is the point of intersection of the two splits. Thus “b” is ruled out by Theorem 2, too. The graphs labeled “c” and “d” feature sprawling triangles, whence they are taken care of by Theorem 1. This completes our combinatorial characterization of the tropically planar graphs of genus at most five. \(\square \)

For genus 6, there are 388 trivalent graphs altogether, 354 of which are planar (Balaban 1976). In Coles et al. (2019) it was shown that 152 tropically planar graphs of genus 6 remain. There are 28 graphs which are non-realizable and could not be ruled out using any prior known criteria; cf. (Coles et al. 2019, Figure 17). Out of these 28 graphs, 19 have a heavy cycle with two loops and can be ruled out using Theorem 2 because the genus is too high. One of the remaining graphs has a sprawling triangle, and thus excluded by Theorem 1. We are left with eight graphs of genus 6, which are shown in Fig. 12; for these we are not aware of any a priori obstruction. There are 672 troplanar graphs of genus 7 according to Coles et al. (2019, Table 1); however, the full list does not seem to be available.

It would be interesting to know how the tropically plane curves of a fixed genus fit into the moduli space of all tropical curves. For genus 3 this was recently answered in terms of modifications by  Hahn et al. (2019).