{'fraction_non_alphanumeric': 0.04913308678737813, 'fraction_numerical': 0.017902598338216225, 'mean_word_length': 3.606471238938053, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Symmetric contact systems of segments, pseudotriangulations and inductive constructions for corresponding surface graphs

We characterise the quotient surface graphs arising from symmetric contact systems of line segments in the plane and also from symmetric pointed pseudotriangulations in the case where the group of symmetries is generated by a translation or a rotation of finite order. These results generalise well known results of Thomassen, in the case of line segments, and of Streinu and Haas et al., in the case of pseudotriangulations. Our main tool is a new inductive characterisation of the appropriate classes of surface graphs. We also discuss some consequences of our results in the area of geometric rigidity theory.


Introduction
There has been much interest recently in adapting results of combinatorial geometry in areas such as geometric rigidity theory, polyhedral scene analysis, or the theory of packings, to a symmetric setting (see [12,Chapters 2,61, 62], for example, for a summary of recent results). Since symmetry is ubiquitous in both natural and artificial structures, much of this work is motivated by applications in materials science, biophysics and engineering. The purpose of this paper is to provide symmetric generalisations of two significant results in combinatorial geometry, which we now describe.
The first result is concerned with an analogue of the well-known planar circle packing theorem of Koebe-Andreev-Thurston, where circles are replaced with line segments. A 2-contact system of line segments in the plane is a finite collection of segments such that any point belongs to at most two segments and belongs to the interior of at most one segment. Thomassen [31] has shown that a graph is the intersection graph of such a contact system of line segments if and only if it is a subgraph of a planar Laman graph.
The second result is concerned with pointed pseudotriangulations, which are plane graphs with straight line edges such that every bounded region is a polygon with exactly three convex angles in its interior, the boundary of the unbounded region is a convex polygon, and such that every vertex has exactly one non-convex incident angle. Such objects have been extensively studied and have found wideranging applications, for example in the solution of the carpenter's rule problem [6], the art gallery problem [28], and even in the description of unusual structural phenomena such as auxeticity in meta-materials (see [2,3,4], for example). A survey of results can be found in [24]. Streinu [29] and Haas et al. [13] have shown the fundamental result that a graph can be realised as a pointed pseudotriangulation if and only if it is a planar Laman graph.
We will prove symmetric versions of the above results in the case where the symmetry group is a cyclic group that is generated either by a rotation or a translation in the plane.
In the case of contact systems of segments, we must take care to specify carefully the appropriate combinatorial object that is analogous to the intersection graph. In the symmetric case, orbits of segments can have multiple intersections and can selfintersect so the graph that arises is naturally a multigraph. Also, we must be careful about non-degeneracy conditions and so we require a very slight modification of the definition of a 2-contact system. We explain the change and its relationship to the one used by Thomassen in more detail below.
Furthermore it is not immediately obvious which classes of graphs are analogous to the plane Laman graphs in the symmetric contexts. Once we identify the relevant classes, which are surface graphs satisfying certain gain-sparsity counts, the main technical difficulty is to provide appropriate inductive characterisations of these classes. These inductive characterisations are, we believe, of independent interest. They are analogous to a widely used result of Fekete, Jordán and Whiteley [11] which gives an inductive characterisation of plane Laman graphs. However, in our setting the proofs require some significant new ideas due to the more complicated topological setting.
In the case of pointed pseudotriangulations, we provide a natural extension of the standard definition in the symmetric setting, and apply our inductive characterisations to establish symmetric versions of the result mentioned above of Streinu and Haas et. al. In particular, this allows us to gain new insights into the rigidity and flexibility properties of bar-joint frameworks with rotational or translational symmetry in the plane.
We summarise the main results of the paper as follows: 1. We characterise, in terms of gain sparsity properties, the intersection graphs of generic symmetric contact systems of line segments in the case where the symmetry group is generated by a rotation of finite order or by a translation (Theorems 5.2 and 5.3).
2. We give an analogous combinatorial characterisation of the graphs of symmetric pointed pseudotriangulations in the case where the symmetry group is generated by a rotation of finite order or by a translation (Theorem 8.3). 3. We show that the relevant gain-sparse surface graphs satisfy a topological extension property, in the sense that they can always be completed to gaintight surface graphs by adding appropriate edges (Proposition 6.4). 4. We give inductive characterisations based on topological vertex splitting moves of the relevant classes of gain-tight surface graphs (Theorems 6.2 and 6.3). 5. We show that a realisation of a planar graph as a bar-joint framework in the plane that is generic with k-fold rotational symmetry, k ≥ 3, is minimally 'forced-symmetric' rigid (i.e. has no symmetry-preserving deformation) if and only if it can be realised as a pointed pseudotriangulation with this symmetry (Corollary 8.5).
These results open up a number of obvious further research directions, such as possible extensions to other discrete subgroups of the Euclidean group, and we hope that this paper serves as an invitation for the reader to join in these explorations.

Comments on the presentation
We have aimed for a relatively self-contained exposition, so some of the minor lemmas presented here with proofs are variations of known results. We have attempted to point out the relevant literature in these cases.
Also because the paper draws on concepts from several different parts of combinatorics, geometry and topology we find it expedient to briefly remind the reader of some elementary concepts and fix notation in Section 2.
Finally, the proofs of the results from points 3 and 4 in the list above are quite long and technical. For that reason we have given precise statements of the results in Section 6 but deferred the proofs til later in order to present the main geometric applications first.

Terminology and notation
Here we fix some terminology and conventions regarding some standard notions of topological graph theory.

Graphs
A graph is a quadruple D = (V, E, s, t) where V, E are sets (of vertices and edges respectively) and s, t are functions E → V . In the literature such objects are sometimes referred to as multi-digraphs or quivers. We shall use graph instead and use adjectives such as simple or loopless as appropriate. We note that graphs can be infinite but all graphs that arise in this paper will be locally finite in the sense that any vertex will be incident to finitely many edges. If the graph D is not clear from the context we will write V (D), respectively E(D), for the sets of vertices, respectively edges, of D. For V ⊂ V , we write E(V ) for the subset of E spanned by V and D(V ) = (V , E(V )) for the subgraph of D induced by V . Similarly for The geometric realisation of D is where (e, 0) ∼ s(e) and (e, 1) ∼ t(e). Throughout the paper we will often conflate vertices or edges of D with the corresponding points or subsets of |D|. Connectivity properties of graphs will play an important role later so we specify our particular definitions here carefully. Given a topological space X and a subset A ⊂ X we say that A separates points u, v if u and v lie in the same path component of X, u, v ∈ A and any continuous path joining u and v must pass through A. We will use this topological notion of separation both in the context of surfaces and graphs.
For example a cutvertex of D will mean a vertex that separates any pair of points in |D|. In particular, any vertex incident to a loop edge is automatically a cutvertex.

Surfaces and surface graphs
A surface Θ is a real two-dimensional manifold without boundary. We will be particularly concerned in later sections with the open annulus A = R 2 − {(0, 0)}. We emphasise here that A is to be thought of purely as a topological manifold. We will use different notation for the various geometric structures that have A as the underlying topological manifold. We note that A has two topological ends, one at zero and one at infinity. The location of these ends relative to various embedded graphs will be of importance later. A Θ-graph G is a pair (D, Φ) where Φ : |D| → Θ is a continuous function that is a homeomorphism onto its image. We will abuse terminology and refer to a subgraph H of G rather than a sub-Θ-graph. In further abusive behaviour we will often conflate vertices and edges of D with their images under Φ. We say that Θ-graphs (D i , Φ i ), i = 1, 2, are isomorphic if there is a homeomorphism h : Θ → Θ and a graph isomorphism k : In particular F is a connected open subset of Θ. We say that F is cellular if it is homeomorphic to R 2 . The boundary ∂F is the subgraph of G comprising those vertices and edges that are contained within the topological boundary of F . The face F has an associated family of closed boundary walks, one for each topological end of the face. For a formal description of these walks in the cellular case (which can be readily adapted to the non-cellular setting), see Chapter 3 of [20]. We say that F is degenerate if there is either a repeated vertex or a repeated edge among all the boundary walks of F and is nondegenerate otherwise. If F is cellular, the degree of F , denoted |F |, is the edge length of its unique boundary walk. In general |F | ≥ |E(∂F )|, |F | ≥ |V (∂F )| and one or both of these inequalities may be strict. A cellular face of degree 3, respectively degree 4, is called a triangle, respectively a quadrilateral.

Contact systems of line segments
A contact system of line segments in the plane is a collection of line segments such that no point is an interior point of more than one segment (see [9] and [14]). A k-contact system is a contact system such that any point belongs to at most k segments. In this scheme the 2-contact systems are in some sense the 'least degenerate' and are thus a natural starting point for investigation. For our purposes we introduce a slightly more restrictive definition as follows. A collection of line segments in the plane is a generic contact system if no point is an interior point of more than one segment and no point is an endpoint of more than one segment. Observe that a generic contact system is necessarily a 2-contact system. On the other hand, we have the following.
Lemma 3.1. Let L be a 2-contact system. There is a generic contact system L (which can be chosen to be arbitrarily close to L) and a bijection L → L , l → l such that l ∩ m = ∅ ⇔ l ∩ m = ∅ Proof. Suppose that l, m ∈ L are distinct and have a common endpoint v. If they are not parallel, then we can extend the segment l by an arbitrarily small length to create a new segment l such that l ∩ m is not an endpoint of l .
If l and m are parallel then we can perturb the common endpoint v by a small amount to create l , m that share a common endpoint but are not parallel. Note that when we do this we also must extend or truncate any other segments k that have an endpoint in l or m to maintain that contact. As long as the perturbation of v is sufficiently small this will be possible without creating any new contacts between segments. Now we are in the situation of the previous paragraph and we extend l as described there.
By repeated applications of the perturbations described above we can find the desired generic contact system L .
Thus, if we are interested in the intersection graphs of such systems, the slightly more restrictive definition of a generic contact system versus that of a 2-contact system is of no consequence. We state the aforementioned result of Thomassen in those terms. Recall that a graph D = (V, E) is (2, 3)-sparse if and only if for every non-empty E ⊂ E, |E | ≤ 2|V (E )| − 3.
Theorem 3.2 (Thomassen, [31]). A graph is the intersection graph of a finite generic contact system of line segments in the plane if and only if it is (2, 3)-sparse.
Note that Lemma 3.1 will need some modification in the symmetric case, which will be our main concern. Details will be given in Section 4.

Embedding the intersection graph
Let L be a generic contact system. The intersection graph of L, which we denote by I L , has vertex set L and directed edges corresponding to pairs (l, m) where the endpoint of l lies in the interior of m. We observe that there is some natural extra structure associated to I L : it comes equipped with a plane embedding as follows. For each l ∈ L we choose a subset c l ⊂ l such that • c l is a closed sub-segment of l that does not contain either of the endpoints of l; • for every m that touches l, c l contains the point of contact (i.e the endpoint of m).
By construction, c l ∩ c m = ∅ for l = m. Thus, if X is the quotient space of R 2 obtained by collapsing each c l to a point v l , it follows that X is homeomorphic to R 2 . The map l → v l provides an embedding of the vertex set of I L in X. If m touches l then the component of m − c m that contains the point of contact maps to a path in X from v m to v l . Thus we have an embedding |I L | → X which we compose with the homeomorphism X → R 2 to construct the desired plane embedding ψ : |I L | → R 2 . Let G L be the plane graph (I L , ψ). See Figure 1 for an illustration of this construction. Of course G L depends on the particular choices of c l for each l and on the choice of homeomorphism X → R 2 . However, it is not hard to see that the combinatorial embedding (see [20], Chapter 4 for definitions) defined by this construction is uniquely characterised by the description above.  On the left we have a contact system with segments l, m, k. In the centre we have indicated the subsegments c l , c m , c k in bold and on the right we have the embedding of the (directed) graph obtained by collapsing each of c l , c m , c k to a point.

Symmetric contact systems
The main objects of interest in this paper are symmetric contact systems. These are contact systems that admit a group action induced by some group of symmetries of the plane. Let Γ be a discrete subgroup of the Euclidean group of isometries of R 2 . See [25,7] for a discussion of the classification of such groups. For g ∈ Γ and X ⊂ R 2 we write g.X for the image of X under g. We consider a contact system of line segments L such that (S1) g.l ∈ L for all l ∈ L, g ∈ Γ In general we will seek analogues of Theorem 3.2 for various different symmetry groups. In order to make the problem more tractable we will impose some conditions relating to finiteness and genericity. In particular we assume that (S2) L has finitely many Γ-orbits Furthermore, we will assume that (S3) L is generic.
Finally we consider an extra condition which is relevant only in the case that Γ does not act freely on R 2 .
(S4) For all l ∈ L and x ∈ l the stabiliser of x in Γ is trivial.
Given L and Γ satisfying (S1-4) we say that L is a generic Γ-symmetric contact system.
Since the notion of 2-contact system is standard in much of the literature we wish to explore the relationship between this notion and that of a generic contact system in the symmetric setting. It is clear that a generic Γ-symmetric contact system is, in particular, a 2-contact system. In the non-symmetric setting Lemma 3.1 provides a partial converse. In the symmetric setting, things are not quite so straightforward.
The following lemma shows that in several cases of interest (S4) is redundant.
Lemma 4.1. Suppose that L, Γ satisfy (S1), (S2). Furthermore suppose that L is a 2-contact system and that Γ does not contain a reflection or a primitive rotation of order 2. Then (S4) is also true.
Proof. Suppose that g.x = x for some non-identity element g ∈ Γ, x ∈ l, l ∈ L. Since g is not a reflection, it must be a rotation and we can assume without loss of generality that g is primitive. Thus g has order at least 3 and it follows that l, g.l and g 2 .l are distinct elements of L that all contain x. This contradicts the assumption that L is a 2-contact system. Now we prove a symmetric analogue of Lemma 3.1.
Then there is a generic Γ-symmetric contact system L arbitrarily close to L and a bijection L → L , l → l such that l ∩ m = ∅ ⇔ l ∩ m = ∅.
Proof. We will show how to adapt the argument for Lemma 3.1. Suppose that l and m are distinct segments in L that have a common endpoint. Case 1: l and m lie in distinct Γ orbits. Then the perturbation argument of Lemma 3.1 carries over to this situation with the understanding that the perturbation is carried out for every element of the orbit of a line segment, respecting the Γ-action.
Case 2: m = g.l for some g ∈ Γ. Let l ∩ m = {v}. Using (S4) we see that v, g.v are distinct endpoints of m. Using (S4) and (S5) we infer that g must be either a rotation of order at least 3 or a glide reflection. If g is a rotation of order at least 3 it follows that m and l are not parallel and that the first perturbation described in the proof of Lemma 3.1 can be also applied in this situation. Finally if g is a glide reflection, and m is not parallel to l then we we can extend one end of l by an arbitrarily small length, and make corresponding extensions to all segments in Γ.l, so that l and m do not share an endpoint. If l and m are parallel then they must both be contained in the axis of the glide reflection g. Now, we can perturb the endpoints of l symmetrically with respect to g, and make corresponding perturbations to all segments in Γ.l and extending or truncating other segments to maintain all other contacts, so that l and m are not parallel and then proceed as before.
Assumption (S5) might seem a little awkward. However we have the following lemma. Lemma 4.3. Suppose that L, Γ satisfy (S1), L is a 2-contact system and Γ contains a rotation of order at least 3. Then L, Γ satisfy (S5).
Proof. Suppose that g.l ∩ l for some segment l ∈ L and translation g ∈ Γ. Then M = ∪ i∈Z g i .l is a line in the plane. Now if h ∈ Γ is a rotation of order at least 3 then h.M ∩ M is a single point and it is clear that this contradicts the fact that L is a 2-contact system.
Later we will focus on the cases where Γ is a cyclic group, generated by either a translation or a rotation. We note that in the case where Γ is generated by a rotation of (finite) order at least 3, Lemmas 4.1, 4.2 and 4.3 allow us to interpret our characterisations of generic Γ-symmetric contact systems as characterisations of Γ-symmetric 2-contact systems. In the cases where Γ is generated by a rotation of order 2 or a translation, things are complicated by the possibility that a symmetric 2-contact system could have a pair of segments that meet at a common endpoint. We defer discussion of such singular orbits to later work as it would significantly add to the length of the present paper and we also believe that our definition of a generic symmetric contact system is reasonably natural and worthy of investigation in its own right.

The surface graph of a symmetric contact system
The orbifold R 2 /Γ is a natural geometric object associated to the group Γ. Let O be the set of non-singular points of R 2 /Γ. Explicitly O is the image of the set of points with trivial stabiliser under the quotient map p : R 2 → R 2 /Γ. We observe that, geometrically, O is a flat surface (i.e. with constant curvature zero). Let Σ be the underlying topological space of O. Later we will be particularly interested in the cases where Γ is generated by a translation or by a rotation and we note that in both of these cases Σ is homeomorphic to A. Now suppose that L is a generic Γ-symmetric contact system in the plane. Using property (S4) of L we see that each Γ-orbit of L defines a local geodesic in O. For l ∈ L, let l : [0, 1] → O be a constant speed geodesic such that l([0, 1]) = p(l) and let L = {l : l ∈ L}. We refer to L as the contact system in O corresponding to L.
More generally, let α : [0, 1] → O be a constant speed local geodesic. We say that x is a point of self intersection of α if there exist t 1 = t 2 such that α(t 1 ) = α(t 2 ). Let N be a finite set of constant speed geodesics in O. We say that N is a generic contact system in O if • any point of intersection of α = β ∈ N is an endpoint of precisely one of α, β and is an interior point of precisely one of α, β, and • any point of self intersection of α ∈ N occurs precisely once as an endpoint of α and precisely once as an interior point of α. Proof. Suppose that L is a generic Γ-symmetric contact system the plane. Suppose that α, β ∈ L, α = β and x is a point of intersection of α and β. Using property (S3) of L it follows that x is an endpoint of precisely one of α, β and an interior point of the other. If x is a point of self-intersection of α then for some l ∈ L, g = e ∈ Γ we must have α([0, 1]) = p(l) = p(g.l). Since g = e, we have g.l = l and again using (S3) we see l and g.l must intersect at an point that is an endpoint of precisely one of l, g.l. Thus x is both an endpoint and an interior point of α as required. The finiteness of L follows from (S2). Thus L is a generic contact system O.
On the other hand suppose that N is a generic contact system in O. It is clear from the construction of N that it satisfies (S1), (S2) and (S4). Suppose that l, m ∈ N have a point in common and that α([0, 1]) = p(l) and β([0, 1]) = p(m) for α, β ∈ N . Then α, β have a point of intersection which is an endpoint of precisely one of α, β. It follows that the point of intersection of l, m is an endpoint of precisely one of l, m. Thus N satisfies (S3). The fact that N is finite implies that N satisfies (S2). Therefore N is a generic Γ-symmetric contact system as required. Now given a contact system N in O we can define a graph I N with vertex set N and edges corresponding to quadruples (α, β, x, y) where α, β ∈ N , x ∈ {0, 1}, y ∈ (0, 1) and α(x) = β(y). Here we allow α = β and moreover it is possible that we could have distinct edges (α, β, x 1 , y 1 ) and (α, β, x 2 , y 2 ). (Note that for some O this can happen even if α = β.) Now we define a Σ-graph whose underlying graph is I N as follows. For each α ∈ N choose a non-empty closed interval c α ⊂ (0, 1) such that y ∈ c α for every edge (β, α, x, y). Now collapse each α(c α ) to a single point p α . The resulting quotient space of O is homeomorphic to Σ. The map α → p α gives an embedding of the vertex set of I N and we use the restriction of α to the appropriate component of [0, 1] − c α to construct embeddings of the edges of I N . Let G N denote the resulting Σ-graph.
So if L is a generic Γ-symmetric contact system in the plane, then Γ acts by directed graph automorphisms on I L and it is easy to see that I L /Γ is canonically isomorphic to I L . Now let Σ = {x ∈ R 2 : Stab Γ (x) = 1 Γ }. It is well known that the restriction p : Σ → Σ is a regular covering projection. Using standard results of covering space theory it follows that we can choose the embedding ψ : |I L | → Σ so that the following diagram commutes where ψ : |I L | → Σ is the embedding constructed above. We note that the left and middle vertical arrows in (1) represent regular covering projections.
In summary a generic Γ-symmetric contact system, L, gives rise to a surface graph, denoted G L , which describes the combinatorial structure of the contact system. See Figure 3 for some examples of generic symmetric contact systems and their corresponding surface graphs.  ) and their corresponding surface graphs (second row). In both cases the surface Σ is homeomorphic to A which we represent topologically by a horizontal strip with top and bottom edges (the dotted lines) identified. The A-graphs L, respectively M , on the left, respectively right, arise as base graphs in the inductive characterisations described in Theorems 6.2 and 6.3.

Gain sparsity counts
For the remainder of the paper we will specialise to the case where the symmetry group Γ is cyclic and orientation preserving. So Γ is either generated by a rotation or a translation. In either of these cases Σ is homeomorphic to the punctured plane A = R 2 − {(0, 0)} so from now on we will primarily be concerned with properties of an A-graph, that is to say a graph together with an embedding of its geometric realisation in A.
Thus D is (2, 3)-sparse if and only if f (C) ≥ 3 for every subgraph C of D that contains at least one edge. If, in addition, f (D) = 3 or D is an isolated vertex, we say that G is (2, 3)-tight or is a Laman graph. Now suppose that G is an A-graph. We say that G is balanced if some face of G contains both ends of A, and unbalanced otherwise. If F ⊂ E(G) then we say that F is balanced, respectively unbalanced, if G(F ) is balanced, respectively unbalanced.
Suppose that l ∈ {1, 2}. We say that G is (2, 3, l)-sparse if f (H) ≥ l for every subgraph H of G, and f (K) ≥ 3 for every balanced subgraph K of G with at least one edge. If in addition, either f (G) = l, or G is balanced and f (G) = 3, or G is an isolated vertex, then we say that G is (2, 3, l)-tight. On the other hand if H is a subgraph of G such that either f (H) < l, or, H is balanced, has an edge and f (H) < 3, then we say that H violates the (2, 3, l)-sparsity count. Since any subgraph of a balanced graph is also balanced it is clear that a balanced A-graph is (2, 3, l)-tight if and only if it is a Laman graph. Remark 5.1. Those familiar with gain graphs will observe that our definition of a balanced A-graph and subsequent definition of (2, 3, l)-sparsity are particular cases of more general notions. See, for example, [33], [30], [15] and [1].
For some examples, see Figure 4. We can also consider the A-graphs shown in Figures 3, 14 and 17. In these diagrams, and elsewhere in the paper, we represent A by a horizontal strip with top and bottom edges identified. Moreover, the directions of the edges of the A-graphs are removed in the diagrams, as they are irrelevant to the sparsity properties of the A-graphs. Specifically the three A-graphs shown in Figure 17 are all (2, 3, 1)-tight. Of the A-graphs in Figure 14, (a) is (2, 3, 2)-tight, (b) and (d) are (2, 3, 1)-tight and (c) is (2, 3, 1)-sparse but not tight. Finally we note that the A-graph L, respectively M , from Figure 3 is (2, 3, 2)-tight, respectively (2, 3, 1)-tight. Now we give the statements of our main results for generic symmetric contact systems.
Theorem 5.2. Let Γ be the subgroup of the Euclidean group generated by a translation or by a rotation of order 2. An A-graph G is the graph of a generic Γ-symmetric contact system of line segments in the plane if and only if G is (2, 3, 2)-sparse. Theorem 5.3. Let Γ be a subgroup of the Euclidean group generated by a rotation of order at least 3. An A-graph G is the graph of a generic Γ-symmetric contact system of line segments in the plane if and only if G is (2, 3, 1)-sparse.

Necessity of the gain sparsity counts
In the remainder of this section we show that the contact systems in Theorems 5.2 and 5.3 have graphs with the required sparsity properties. First, since we need it later and to make our presentation more self-contained, we give a proof of the corresponding part of Thomassen's result in the non-symmetric case (Theorem 3.2).
Let L be a generic contact system of line segments in the plane and let deg + (l) denote the outdegree of a vertex l ∈ V (I L ) = L. We say that an endpoint of l is free if it does not lie in the interior of any other segment.
is the total number of free endpoints in L.
Theorem 5.4. If L is a non-empty collection of line segments in the plane, then Proof. Note that it suffices to check the sparsity condition for all induced subgraphs (V, E) of I L (i.e. subgraphs corresponding to subsets L of L) with at least one edge. Thus we must show that there are at least three free endpoints in L .
Choose a segment l ∈ L . Without loss of generality we may assume that l is parallel to the y-axis: just rotate the entire configuration until that is true. Now pick some interior point of l as a starting point and move downwards along l until we come to the endpoint. If it is free then we have found a free endpoint. If it is not free then it belongs to the interior of some other segment m since L is a generic contact system. Move along m in a direction that does not increase the y-coordinate and continue in this way. Eventually we must arrive at our first free endpoint p 1 . By applying the same argument but moving upward from our starting point we find another free endpoint p 2 . Now p 1 = p 2 since the y-coordinate of p 1 , respectively p 2 , is strictly less, respectively greater, than that of the starting point. Now let M be the line containing p 1 and p 2 . Since E is not empty, not every line segment in L is contained in M . Thus there is a point in some segment of L that is not in M . Start at this point and move along segments always in a direction that does not decrease the perpendicular distance to M . Eventually we must arrive at a free endpoint p 3 that does not lie in M and therefore is not p 1 or p 2 .

The symmetric cases
Now suppose that Γ is generated by a single rotation or a single translation and let L be a Γ-symmetric contact system of line segments. As noted above Σ ≡ A.
Proposition 5.5. Suppose that G L is a balanced A-graph. Then there is a transversal F of the Γ-orbits of L such that (l, m) ∈ E(I L ) if and only if there is some g ∈ Γ such that (g.l, g.m) ∈ E(I F ). In particular I L ∼ = I F .
Proof. Since G L = (I L , ψ) is a balanced A-graph, it is clear that ψ : |I L | → A induces a trivial homomorphism of fundamental groups. Using the commutativity of the left hand square of (1) and some standard results of covering space theory it follows that the covering projection |I L | → |I L | has a global section σ : ) yields the required transversal of the orbits of L.
Corollary 5.6. Suppose that Γ = z where z is either a translation or a rotation and that L is a generic Γ-symmetric contact system of line segments in the plane.
If H is a balanced subgraph of G L that contains at least one edge then f (H) ≥ 3.

Proof. If H is an induced subgraph then it is clear that
If H is not induced then it can be obtained from some G L by shortening some of the segments in L so as to remove the necessary edges. In either case H = G M for some generic Γ-symmetric contact system M. Using Proposition 5.5, since H is balanced, we see that H ∼ = G F for some finite contact system F. By Theorem 5.4 it follows that f (H) ≥ 3.
To identify the necessary sparsity condition for unbalanced subgraphs, we first observe that f (G L ) is equal to the number of Γ-orbits of free ends in L.
Theorem 5.7. Suppose that Γ is generated by a translation and let L be a generic Γ-symmetric contact system of line segments in the plane. Then the graph G L is (2, 3, 2)-sparse.
Proof. By Corollary 5.6 it suffices to show that f (K) ≥ 2 for any non-empty subgraph K of G L . Clearly we can assume that K is an induced subgraph. Also we can assume that the generator of Γ is the translation (x, y) → (x + 1, y).
Let M be the Γ-invariant subset of L that corresponds to V (K). If all line segments in M are horizontal then, since we assume that L is generic, it is clear that K has no edges and since it has at least one vertex, it follows that f (K) ≥ 2.
So we may assume that some segment l ∈ M is not horizontal. Now starting at an interior point of l we can move along segments so that the y-coordinate is nondecreasing. Since L must be contained within some horizontal strip, as it has finitely many Γ-orbits and each orbit is bounded in the y-direction, we must eventually arrive at a free endpoint. Similarly there is another free endpoint obtained by moving away from the starting point along line segments so that the y-coordinate is non-increasing. These two free endpoints do not lie in the same orbit of Γ since they have different y-coordinates. Thus f (K) ≥ 2 as required.
Next we consider the case where Γ is generated by a rotation.
Theorem 5.8. Suppose that Γ is generated by a rotation of order n and that L is a generic Γ-symmetric contact system of line segments in the plane. Then Proof. As in the proof of Theorem 5.7 let K be a non-empty induced subgraph of G L and let M be the Γ-invariant subset of L that corresponds to V (K). We must show that M has at least two free endpoints that lie in different Γ-orbits.
Let o be the fixed point of Γ. Choose l ∈ M. Starting at an interior point of l, move along segments in M so that the distance to o is always increasing. Since M lies inside some bounded region of the plane we must eventually arrive at a free endpoint, p. Thus f (K) ≥ 1. This proves the first statement. Now suppose that n = 2 and let L be the line containing the points p and o. If K has no edges then, since it has at least one vertex, we have f (K) ≥ 2. On the other hand, if K has an edge then not every segment in M is contained in L. Starting at some point in a segment of M that is not in L, move along segments in such a way that the perpendicular distance to L is non-decreasing. Again we must eventually arrive at some free endpoint q. Now since q ∈ L and Γ.p ⊂ L (here is where we use the n = 2 hypothesis) we have found two free endpoints that lie in different Γ orbits. Thus f (K) ≥ 2 in this case.
6 Properties of (2, 3, l)-tight A-graphs: statements In the previous section we established one direction of Theorems 5.2 and 5.3. In order to establish the other direction we need to investigate various properties of (2, 3, l)sparse graphs. In this section we present the statements of the necessary results. Since the proofs are quite long and are essentially independent of the geometric applications, we defer those til later.
Let Θ be a surface and suppose that G is a Θ-graph with a triangular face T and an edge e = uv that belongs to the boundary walk of T . We also suppose that u = v. Let G e,T be the Θ-graph obtained by collapsing |e| (the image of e in Θ) to a point and deleting one of the other edges of the facial walk of T . We say that G e,T is obtained from G by a topological contraction of T along e. On the other hand we say that G is obtained from G e,T by a triangular vertex split. It is to be emphasised that, apart from the case explicitly specified in the definition, parallel edges or loop edges that are created by the edge contraction are retained in G e,T . In [11] Fekete, Jordán and Whiteley prove the following inductive characterisation of plane Laman graphs.
Theorem 6.1 (Fekete, Jordán and Whiteley). Suppose that G is a plane Laman graph with at least 3 vertices. Then G can be constructed from a single edge by a sequence of triangular vertex splits.
We would like to prove results analogous to Theorem 6.1 for (2, 3, l)-tight Agraphs for l ∈ {1, 2}. However it is easy to see that there are infinitely many pairwise non-isomorphic (2, 3, l)-tight A-graphs that have no triangular faces. Thus we will need to consider an additional contraction move to deal with quadrilateral faces.
Suppose that Q is a quadrilateral face of G with boundary walk v 1 , e 1 , v 2 , e 2 , v 3 , e 3 , v 4 , e 4 , v 1 such that v 1 = v 3 . Let δ be a Jordan arc joining v 1 and v 3 whose relative interior lies in Q. We can view δ as a (topological) edge that is not in G.
We will refer to δ as the diagonal of Q joining v 1 and v 3 . Let G v 1 ,v 3 ,Q be the Θ-graph obtained from G ∪ δ by contracting δ to a point and then deleting one of the edges e 1 , e 2 and one of the edges e 3 , e 4 . We call G v 1 ,v 3 ,Q a quadrilateral contraction of G. On the other hand we say that G is obtained from G v 1 ,v 3 ,Q be a quadrilateral vertex split. Again we emphasise that, apart from the cases explicitly specified in the definition, parallel edges or loop edges that are created by the contraction of δ are retained in G v 1 ,v 3 ,Q . See Figure 5 for illustrations of triangle and quadrilateral contractions. We note here that in all the cases that arise in our later discussion the quadrilateral Q will have at least three distinct edges. So we will always assume (tacitly) that the deleted edge from the set {e 1 , e 2 } is distinct from the deleted edge from the set {e 3 , e 4 }. This assumption is not necessarily vacuous in the case where Q is a degenerate quadrilateral.
Then there is a sequence of (2, 3, 2)-tight A-graphs G 0 , G 1 , . . . , G n ∼ = G where |V (G 0 )| = 2 and for i = 1, . . . , n, G i is obtained from G i−1 by either a triangular vertex split or a quadrilateral vertex split. Moreover, if G is unbalanced then G 0 ∼ = L, whereas if G is balanced then G 0 ∼ = K and only triangular vertex splits are required.
Proof. See Section 10. Theorem 6.3. Suppose that G is a (2, 3, 1)-tight A-graph with at least one edge. Then there is a sequence of (2, 3, 1)-tight A-graphs G 0 , G 1 , . . . , G n ∼ = G where |V (G 0 )| ≤ 2, and for i = 1, . . . , n, G i is obtained from G i−1 by either a triangular vertex split or a quadrilateral vertex split. Moreover, if G is unbalanced then G 0 ∼ = M , whereas if G is balanced then G 0 ∼ = K and only triangular vertex splits are required.
The final piece of the puzzle, at least on the combinatorial side of things, is to clarify the relationship between sparse and tight graphs. It is well known that any (2, 3)-sparse graph D can be completed to a (2, 3)-tight graph by adding appropriate edges to D. This follows from the fact that the edge sets of (2, 3)-sparse subgraphs of the complete graph K |V | form an independence structure of a matroid, called the generic 2-rigidity matroid (see, e.g., [32]). Similarly, it is known that the (2, 3, )sparsity count induces a matroid for ∈ {1, 2} (see [30,21], for example).
However, in the context of surface graphs it is not always clear that these matroidal augmentation properties respect the topological embedding. For example it is known that for any simple graph the (2, 0)-sparse edge sets form the independent sets of a matroid. Now consider the complete graph K 5 , which is (2, 0)-tight and can be embedded in the torus. However if e is an edge of K 5 we observe that there is an embedding of the (2, 0)-sparse graph K 5 − e in the torus that cannot be extended to an embedding of K 5 . By way of analogy we draw the reader's attention to the fact, as observed for example by Diestel (see [10], Chapter 4), that it is not immediately obvious that a maximal plane graph is maximally planar. Diestel provides a careful proof that this is indeed the case in loc. cit. One might view Proposition 6.4 as an analogue of that classical fact for certain classes of surface graphs. Proposition 6.4. Let l ∈ {1, 2} and let G be a (2, 3, l)-sparse A-graph. There exists a (2, 3, l)-tight A-graph G such that G is a spanning subgraph of G .

Sufficiency of the counts
In this section we complete the proofs of Theorems 5.2 and 5.3. We have already shown in Section 5 the necessity of the sparsity conditions in each of these theorems. So this section is devoted to proving the sufficiency. Suppose that G is an A-graph associated to a generic Γ-symmetric contact system and that e ∈ E(G). Suppose that e = Γ.(l, m) where l and m are segments in the contact system. By shortening all the segments Γ.l a little bit we obtain a generic symmetric contact system whose A-graph is G − e. Thus, in light of Proposition 6.4 it suffices to prove the following result.
Proposition 7.1. Let G be a (2, 3, l)-tight A-graph where l ∈ {1, 2}. For l = 1, respectively l = 2, let Γ be a discrete subgroup of the Euclidean group generated by a rotation of order at least 3, respectively a translation or a rotation of order 2. Then there is some generic Γ-symmetric contact system L such that G L ∼ = G.
Proof. First observe that by Lemma 4.4 it suffices to show that there is some contact Figure 3 for illustrations of the required contact systems. Now suppose that |V (G)| ≥ 3. By Theorems 6.2 and 6.3 we can find some (2, 3, l)-tight A-graph G such that G is either a triangle contraction of G or a quadrilateral contraction of G. By induction the A-graph G has a representation by a contact system in O, say N . So it suffices to show that the corresponding triangle splitting or quadrilateral splitting moves are representable by contact systems in O. In both cases we must replace a single geodesic l ∈ N by a pair of segments so that the contacts of the new segments correspond to the appropriate subsets of the neighbours of l.
In Figure 6 we illustrate the possibilities for triangle splits. In each case the solid segment l is replaced by two segments l and l which both contact the segment w. We observe that • The segments l , l can be chosen to lie in an arbitrarily small neighbourhood of the original segment l. Thus if m is a segment that is adjacent to l (considered as vertices in G ) then we can ensure that there is a corresponding intersection point between m and one of l , l • The point of contact between l and l can be chosen to ensure that the set of segments intersecting with l , respectively l correspond to the neighbour sets of l , respectively l in G N .
In Figure 7 we see the corresponding diagrams for quadrilateral splits. In this case we observe that the line segment l can be replaced by two parallel segments l , l that are arbitrarily close to the original segment l and that realise the given quadrilateral splitting move.
Finally, we observe that these geometric constructions, both for triangle splits and quadrilateral splits, apply even in the case where one or more of the split edges involving l is a loop edge.
So in all cases the required spitting moves are realisable by generic contact systems and the result follows by induction.

Pseudotriangulations
In this section we give another application of our combinatorial results to pseudotriangulations on flat surfaces, which naturally arise from symmetric pseudotriangulations in the plane. For a comprehensive survey on pseudotriangulations and their applications we refer the reader to [24]. See also the recent work by Borcea and Streinu on periodic pseudotriangulations (see [3], for example).
Note that while in other sections of the paper a graph is understood to be directed, throughout Section 8 exceptionally we understand graphs as undirected.

Pseudotriangulations on flat surfaces
A simple undirected graph with straight line edges is called a geometric graph. For a discrete subgroup Γ of the Euclidean group, we say that a geometric graph G = (V, E) is Γ-symmetric if for all e ∈ E and all g ∈ Γ, we have g.e ∈ E, where the edge e is considered as a line segment in the plane and g.e denotes the image of the line segment e under the linear transformation defined by g. Throughout this section, we assume that G is a plane geometric graph (i.e., G has no crossing edges) and that Γ acts freely on the vertices and edges of G.
Recall from Section 4 that the flat surface consisting of the non-singular points of R 2 /Γ is denoted by O. We assume throughout this section that Γ is either the trivial group, or is generated by a translation or rotation, and hence O is the plane, a flat cylinder, or a flat cone (with the cone point removed) with cone angle 2π/k, k ≥ 2. Note that under this quotient map each Γ-orbit of edges of a Γ-symmetric geometric graph is mapped to a locally geodesic line segment in O. Thus, a Γsymmetric geometric graph G naturally gives rise to an embedding of the quotient graph of G with locally geodesic edges in O, which we call a geometric O-graph. Note that if Γ is non-trivial then the underlying surface graph is an A-graph.
For a (possibly degenerate or non-cellular) face F of a geometric O-graph, we say that a vertex in the boundary of F is convex if the internal angle (with respect to F ) of the boundary at this vertex is convex, that is, strictly smaller than π. A pseudotriangle is a cellular face of G with exactly three convex vertices. A vertex v of G is called pointed if there are two consecutive edges incident with v which form an angle that is strictly larger than π.
A geometric O-graph is called a pointed pseudotriangulation in O if G is connected, every vertex of G is pointed, and every face of G has a minimum number of convex vertices in its boundary. Note that this implies that every cellular face of a pointed pseudotriangulation G in O is a pseudotriangle. Moreover, if O is the plane, then the unbounded face of G has no convex vertices. Similarly, if O is a flat cylinder, then each unbounded face of G has exactly one convex vertex, and if O is a cone with cone angle 2π/k, k ≥ 2, then the unbounded face of G has no convex vertices, whereas the face of G containing the cone point has exactly two convex vertices if the cone angle is π, and exactly one convex vertex otherwise. Finally, if O is a flat cylinder or cone and the A-graph of G is balanced, then the non-cellular face must have no convex angles. See Figure 8 for some examples.
It was shown in [29] that the graph of any pointed pseudotriangulation in the plane is (2, 3)-tight. Conversely, it was shown in [13] that every planar (2, 3)-tight graph can be embedded as a pointed pseudotriangulation in the plane (see also [11]). Using Theorems 6.2 and 6.3 we can extend these results to pointed pseudotriangulations on other flat surfaces.
We have the following necessary condition for a geometric graph to be a pointed pseudotriangulation in O. The proof of this result adapts a counting argument in [29]. For the sparsity counts, let G be a subgraph of G and let m , n and f be the number of vertices, edges and faces of G . Suppose first that G is unbalanced. Since pointedness is a hereditary property, and since each cellular face of G must have at least three convex angles and the non-cellular faces must have at least two convex angles in total, we have 2m − n ≥ 3f − 4. This implies that m ≤ 2n − 2. If G is balanced, then as above it is isometric to a geometric plane-graph and we have 2m − n ≥ 3(f − 1). Hence m ≤ 2n − 3.
Note that if O is a cone with cone angle 2π/k, where k ≥ 3, then c = 3(f −2)+1. By the same argument as above, it then follows that G is (2, 3, 1)-tight.
We will now show that the converse of Proposition 8.1 holds.
If O is a flat cylinder or flat cone with cone angle π, then for any (2, 3, 2)-tight A-graph G there exists a pointed pseudotriangulation in O whose A-graph is G. Similarly, if O is a flat cone with cone angle 2π/k, k ≥ 3, then for any (2, 3, 1)-tight A-graph G there exists a pointed pseudotriangulation in O whose A-graph is G.
Proof. Let G be a (2, 3, 2)-tight ((2, 3, 1)-tight, respectively) A-graph. If G is balanced, then it follows from [13, Theorem 1] that G can be realised as a pointed pseudotriangulation in the plane, and hence (via an isometric embedding of the corresponding subset of the plane) also as a pointed pseudotriangulation in O. Let G 0 , . . . , G n = G be the construction sequence for G from Theorem 6.2 (if G is (2, 3, 2)-tight) or Theorem 6.3 (if G is (2, 3, 1)-tight). In each case we may clearly construct a pointed pseudotriangulation in O whose A-graph is G 0 . See Figure 9 for an illustration. In each step of the construction sequences, G i is obtained from G i−1 by a triangular or quadrilateral vertex split. We suppose that G i−1 is embedded as a pointed pseudotriangulation in O, and show that the position of the new vertex can be chosen in such a way that the resulting geometric O-graph is again a pointed pseudotriangulation in O whose A-graph is G i .
Suppose first that G i is obtained from G i−1 by a triangular vertex split applied to the vertex v along the edge e = vw. More precisely, if we write the edges of G i−1 that are incident with v in counterclockwise order as (e, f 1 , . . . , f t ), then without loss of generality G i is obtained from G i−1 by adding a new vertex v so that v is adjacent to v and w via two new edges, the edges f 1 , . . . , f s for 1 ≤ s ≤ t (or none of the edges f i ) are replaced with the edges f i , where f i is obtained from f i by changing the end vertex v to v , and the remaining edges f s+1 , . . . , f t , e remain incident with v. Note that any loop appears twice in the list (e, f 1 , . . . , f t ). In particular, if e is a loop, then it appears again as an edge f s+ for some ≥ 1 since e remains unchanged by the triangular vertex split. If f i is a loop, however, which appears again in the list as f i with i < i , then we may have i ≤ s and i > s, i.e. the triangular vertex split may change the loop edge f i to a non-loop edge.
Since G i−1 has been embedded as a pointed pseudotriangulation in O, there exists a line segment L containing v so that all edges incident with v emanate from v on the same side of L. We consider three distinct cases depending on the position of the edges incident with v in their counterclockwise order from L. In each case it is straightforward to see that the resulting geometric O-graph is a pointed pseudotriangulation in O. See also Figure 10. Suppose next that G i is obtained from G i−1 by a quadrilateral vertex split of v along the edges e 1 = vw and e 2 = vx. More precisely, if we write the edges of G i−1 that are incident with v in counterclockwise order as (e 1 , f 1 , . . . , f s , e 2 , f s+1 , . . . f t ), then without loss of generality G i is obtained from G i−1 by adding a new vertex v so that v is adjacent to w and x via two new edges, the edges f 1 , . . . , f s (which may not exist) are replaced with the edges f i , where f i is obtained from f i by changing the end vertex v to v , and the remaining edges e 1 , e 2 , f s+1 , . . . , f t remain incident to v.
Since G i−1 has been embedded as a pointed pseudotriangulation in O, there exists a line segment L containing v so that all edges incident to v emanate from v on the same side of L.
Suppose first that the quadrilateral created by the quadrilateral vertex splitting move is non-degenerate, that is, the vertices v, v , w and x are all pairwise distinct. Then we consider two distinct cases depending on the position of the edges incident with v in their counterclockwise order from L. In each case it is straightforward to check that the resulting geometric O-graph is a pointed pseudotriangulation in O. See also Figure 11. Figure 11: For x = 1, 2, row x illustrates Case x for placing the new vertex v in a quadrilateral vertex split of G i−1 to obtain another pointed pseudotriangulation in O.
Suppose next that the quadrilateral created by the quadrilateral vertex split is degenerate. Then the A-graph of the quadrilateral is one of the three graphs depicted in Figure 14 In case (c), we again consider the list of edges that are incident to v in the pointed pseudotriangulation G i−1 in O in counterclockwise order from L. In this list, the edge f = vx may either lie between the two copies of the loop e, or between a copy of e and L. In the first case, we illustrate how to place the new vertex v to obtain another pointed pseudotriangulation in O in Figure 13. The other case is similar.
We may reformulate Proposition 8.1 and Proposition 8.2 in terms of coverings of Figure 12: The two rows illustrate how to place the new vertex v in a quadrilateral vertex split of G i−1 to obtain another pointed pseudotriangulation in O, where the new quadrilateral has the A-graph shown in Figure 14 pointed pseudotriangulations in O as follows. We say that a Γ-symmetric geometric graph G is a Γ-symmetric pointed pseudotriangulation in the plane if its quotient graph G/Γ is a pointed pseudotriangulation in the flat surface O of non-singular points of R 2 /Γ. Theorem 8.3. Let Γ be generated by a translation or a 2-fold rotation (n-fold rotation with n ≥ 3) in the plane. Then the quotient A-graph of a Γ-symmetric pointed pseudotriangulation in the plane is (2, 3, 2)-tight ((2, 3, 1)-tight, respectively). Conversely, for any (2, 3, 2)-tight ((2, 3, 1)-tight, respectively) A-graph G there exists a Γ-symmetric pointed pseudotriangulation G in the plane whose quotient A-graph is G.
Remark 8.4. Since the orbifolds considered in this section arise from a discrete subgroup of the Euclidean group acting on the plane, the cone angle of the flat cone O in Propositions 8.1 and 8.2 is assumed be of the form 2π/k for k ≥ 2. However, the proofs can easily be adapted to extend these results to flat cones with any cone angle α, 0 < α ≤ 2π. Observe that for the number c of convex angles in a pointed pseudotriangulation with f faces in the cone O with cone angle α we have , so the corresponding sparsity counts change accordingly. In fact, this pattern for the counts continues in this fashion for cone angles α > 2π, with c = 3(f − 2) + a if (a − 1)π ≤ α < aπ.

Applications in geometric rigidity theory
We now discuss some applications of the results in Section 8.1 to the rigidity and flexibility analysis of symmetric bar-joint frameworks. We refer the reader to the Handbook chapter on Rigidity and Scene Analysis by Schulze and Whiteley [12, Chapter 61] for a detailed summary of definitions and results in geometric rigidity theory.
A (bar-joint) framework in the plane is a pair (G, p), where G = (V, E) is a simple undirected graph and p : V → R 2 is an embedding. We think of (G, p) as a collection of fixed-length bars (corresponding to the edges of G) which are connected at their ends by pin joints (corresponding to the vertices of G). Note that a framework in which no edges cross each other may be considered as a geometric graph in the plane. Loosely speaking, a framework (G, p) is rigid if all edge-length preserving, continuous motions of (G, p) are trivial, i.e. rigid body motions in the plane, and flexible otherwise. A framework (G, p) is generic if the coordinates of the points p(v), v ∈ V , are algebraically independent over Q.
It is well known that a graph G is (2, 3)-tight if and only if G is minimally 2rigid, that is, any generic realisation of G as a bar-joint framework in the plane is minimally rigid (in the sense that removing any edge yields a flexible framework) [22,17]. Pointed pseudotriangulations allow us to give a geometric certificate for a planar graph to be minimally 2-rigid, since a planar graph is (2, 3)-tight if and only if it can be embedded as a pointed pseudotriangulation in the plane.
Using the results in Section 8.1 we may deduce symmetric analogues of this result. We need the following definitions. For an abstract group C, we say that a graph G is C-symmetric if there exists a group action θ : C → Aut(G), where Aut(G) denotes the group of automorphisms of G. We will assume throughout this section that θ is free, i.e. it acts freely on the vertex and edge set of G. Let G be a C-symmetric graph and suppose that C also acts on R d via a homomorphism τ : C → O(R d ). Then a framework (G, p) is called C-symmetric (with respect to θ and τ ) if τ (g)(p(v)) = p(θ(g)(v)) for all g ∈ C and v ∈ V.
A C-symmetric framework (G, p) is called (forced) C-rigid if there are no nontrivial motions of (G, p) that preserve the full symmetry of (G, p), in the sense that all frameworks along the path are also C-symmetric (see [26] for more details). Further, (G, p) is called C-generic if the representatives for the C-orbits of vertices of G are in generic position. A graph G is called minimally C-rigid (with respect to θ and τ ) if some (or equivalently, every) C-generic realisation of G (with respect to θ and τ ) as a bar-joint framework is minimally C-rigid in the plane. C-rigidity has been studied extensively in various different contexts in recent years; see for example [15,19,21]. A detailed summary of results can be found in [12,Chapter 62].
Corollary 8.5. Let G be a C-symmetric planar graph with respect to the free action θ : C → Aut(G), where C is a cyclic group of order k ≥ 1, k = 2. Then G is minimally C-rigid with respect to θ and τ , where τ (C) is generated by a rotation of order k in the plane, if and only if G can be embedded as a τ (C)-symmetric pointed pseudotriangulation in the plane (with respect to θ).
Proof. Given a C-generic (with respect to θ and τ ) minimally C-rigid framework with no edges crossing each other, we consider the corresponding geometric quotient graph G in the flat cone O of non-singular points in R 2 /τ (C). By [15,Theorem 6.3], the A-graph G of G is (2, 3, 1)-tight. Thus, by Corollary 8.3, there exists a τ (C)-symmetric pointed pseudotriangulation in the plane (with respect to θ) whose quotient A-graph is G . Conversely, if G can be embedded as a τ (C)-symmetric pointed pseudotriangulation in the plane (with respect to θ), then, by Corollary 8.3, the quotient A-graph of G is (2, 3, 1)-tight. Thus, by [15,Theorem 6.3], G is minimally C-rigid with respect to θ and τ .
While rigidity always implies C-rigidity, the converse is not true in general. However, note that if C is a cyclic group of order k = 1, 3, then C-rigidity is in fact equivalent to rigidity for C-generic frameworks. This is trivial for k = 1 and was shown in [27, Theorem 6.11] for k = 3.
For the case when τ (C) is generated by a rotation of order 2, we conjecture that a result analogous to Corollary 8.5 may be established by allowing the action θ to be non-free on the edges of G, and hence allowing an edge of G to go through the cone point of R 2 /τ (Γ). By the transfer results for C-rigidity established in [5], this result would then immediately also extend to the case of reflection symmetry.
Rigidity analyses of periodic frameworks in the plane, or equivalently, frameworks on the flat torus, have also received a significant amount of attention in recent years, both under a fixed torus (see [23,30,16], for example) and a flexible torus (see [1,18], for example). In particular, it was shown in [3] that a pointed pseudotriangulation on the flat torus has exactly one non-trivial motion under a fully flexible torus, and that this motion is expansive in the sense that it does not decrease the distance between any pair of vertices. We conjecture that this result extends to the case of pointed pseudotriangulations on the flexible flat cylinder. In the case when the cylinder is fixed, it follows from [16,Theorem 2.4] and the results in Section 8.1 that generic realisations of G as frameworks on the cylinder (or equivalently, frameworks in the plane that are periodic in one direction) are minimally rigid if and only if G can be embedded as a pointed pseudotriangulation in the flat cylinder.
Remark 8.6. We conclude this part of the paper by noting that the results of Sections 5, 7 and 8 suggest several obvious lines of future work. In particular it would be interesting to prove analogues of Theorems 5.2, 5.3 and 8.3 for all of the discrete subgroups of the Euclidean group. We have conjectures for various cases. However the inductive characterisations of the appropriate surface graphs seem to be significantly more challenging in these cases.

Unions and intersections
The remainder of the paper is devoted to proving the results of Section 6. In this section we set out some elementary properties of balanced and unbalanced A-graphs, and the associated gain sparsity counts. See [33], [15] and [30] for more detail on gain graphs and associated matroids.
First we record the fundamental observation that for subgraphs B, C of D, Now suppose that D is a (2, 3)-sparse graph. It is easy to see using Equation (2) that if B is (2, 3)-tight then B is connected. Furthermore if B and C are both (2, 3)-tight and B ∩ C contains at least one edge then both B ∪ C and B ∩ C are (2, 3)-tight. We will generalise these observations to (2, 3, l)-sparse A-graphs. Throughout the section G is an A-graph and H and K are non-empty subgraphs of G.
The following lemma is a special case of [15,Lemma 2.4].
Lemma 9.1. Suppose that H and K are both balanced and H ∩ K is connected. Then H ∪ K is also balanced.
Proof. Suppose that H ∪ K is unbalanced. Let F be the face of H that contains the ends of A. There must be a path p in K joining vertices u, v ∈ ∂F ∩ K such thatp ⊂ F ∩ K andp separates the ends of A in F , wherep is the relative interior of p. Let q be a path in H ∩ K joining u and v. The concatenation of p and q forms a loop in K that separates the ends of A contradicting the hypothesis that K is balanced.
1. If H and K are both unbalanced and H ∩ K is non-empty, then H ∩ K and H ∪ K are both (2, 3, 2)-tight. Furthermore H ∩ K is either unbalanced or consists of a single vertex.
2. If at least one of H or K is balanced and H ∩ K has at least two vertices then H ∪ K is (2, 3, 2)-tight. Furthermore either H ∩ K is (2, 3, 2)-tight or, H ∩ K consists of two isolated vertices and H ∪ K is unbalanced.
Proof. If H and K are both unbalanced then, by (2) We have a similar statement for (2, 3, 1)-sparse graphs. The proof is a routine adaptation of the proof of Lemma 9.3 and we omit the details. Lemma 9.4. Suppose that G is (2, 3, 1)-sparse and that H, K are both (2, 3, 1)-tight.
1. If H and K are both unbalanced and H ∩ K is non-empty, then H ∩ K and H ∪ K are both unbalanced and (2, 3, 1)-tight.
2. If at least one of H or K is balanced and H ∩ K has at least one edge then H ∪ K is (2, 3, 1)-tight.

Inductive constructions for tight graphs
Throughout this section G is a (2, 3, l)-tight A-graph. Since a balanced A-graph is equivalent to a plane graph with a puncture in the unbounded face we can restate Theorem 4 of [11], which we will need later, as follows.
Theorem 10.1 (Fekete, Jordán, Whiteley). Suppose that G is a balanced (2, 3, l)tight A-graph with at least 4 vertices. Then for each vertex v of G there are distinct edges e 1 , e 2 , both not incident with v and triangles T i containing e i such that G e i ,T i is also (2, 3, l)-tight for i = 1, 2.

Euler counts
Let S = {x ∈ R 3 : x = 1} be the standard 2-sphere and suppose that G is a connected finite S-graph with at least one edge. In particular, all faces of G are cellular with positive degree. Let f i be the number of faces of degree i. Since we allow loop edges and parallel edges, it is possible that f 1 or f 2 are non-zero. Using Euler's polyhedral formula, i≥1 f i = 2 + |E| − |V |, together with i≥1 if i = 2|E| and f (G) = 2|V | − |E|, we have for a connected S-graph with at least one edge. From this we can deduce the following for A-graphs. (See Figure 4 for some examples.) Lemma 10.2. Suppose that l ∈ {1, 2} and that G is a (2, 3, l)-tight A-graph with at least three vertices.
(1) If G is balanced, it has at least one triangular face.
(2) If G is unbalanced and has no triangular face then every cellular face has degree 4. (1) is a standard fact about plane Laman graphs. So assume that G is unbalanced. For the purposes of the proof (as opposed to the statement), think of G as an S-graph with two marked faces corresponding to the faces that contain the ends of A. Suppose that l = 2. In this case loop edges are forbidden, so f 1 = 0. Also if F is a face of degree two then F must be one of the marked faces, otherwise the boundary ∂F (recall Section 2.2) is balanced and f (∂F ) = 2. Conclusion (2) now follows easily from Equation (3). Now suppose that l = 1 and f 3 = 0. Then, using Equation (3), we have 3f 1 + 2f 2 ≥ 6 with equality if and only if f i = 0 for i ≥ 5. If F is a face of G with |F | = 2 then, since G has at least three vertices, F must have non-degenerate boundary otherwise we have a vertex with two incident loop edges which is forbidden by (2, 3, 1)-sparsity. Thus any face of degree at most two must be one of the marked faces. It follows that f 1 = 2, f 2 = 0, and thus as remarked above, f i = 0 for i ≥ 5.

Triangles
Suppose that G is a (2, 3, l)-sparse A-graph and that T is a triangular face of G. If l = 2 then the boundary of T must be non-degenerate (i.e. there is no repeated vertex in the boundary walk). In the case l = 1, either T is non-degenerate or ∂T is isomorphic to Figure 14(d). a (2, 3, 1)-sparse A-graph and that T is a degenerate triangular face. If e is a non-loop edge of T then G e,T is also (2, 3, 1)-sparse.
Proof. Let u, v be the vertices of ∂T and let z be the corresponding contracted vertex of G e,T . If H is a (balanced or unbalanced) subgraph of G e,T that violates the (2, 3, 1)-sparsity count then it is easy to see that V (H) − {u, v} ∪ {z} spans a subgraph G that also violates the (2, 3, 1)-sparsity count.
So we can assume from now on that all triangular faces are non-degenerate. Note that if l = 2 then we can assume that the subgraphs A and B from the proof above are induced subgraphs of G e,T and G respectively. In particular B does not contain the vertex of T that is not incident to e in this case. This is not necessarily true when l = 1. See Figure 17 for an example.
The graph B whose existence is asserted by Lemma 10.4 is called a blocker for the contraction G e,T . Observe that B has a face that properly contains the face T of G.
Lemma 10.5. Suppose that G is (2, 3, l)-tight and that B is a blocker for G e,T that is maximal with respect to inclusion among all such blockers. If F is a face of B that does not contain T then F is also a face of G.
Proof. We will deal with the case in which G is unbalanced. The argument for the balanced case is similar and easier. Let H, respectively K, be the subgraph of G consisting of ∂F together with all edges and vertices of G that are inside, respectively outside, F . Observe that H ∪K = G and H ∩K = ∂F .
Combining these we see that The only other possibility is that B is balanced and B ∪ H is unbalanced. In this case, F must be the face of B that contains both ends of A. Since F is also a face of K, it follows that K must also be balanced and f (K) ≥ 3. Now the first equation in (4) yields f (B ∪ H) ≤ l. Therefore B ∪ H is an unbalanced blocker that strictly contains B, contradicting the maximality of B.
We note that the case of Lemma 10.5 in which G is balanced is equivalent to Lemma 9 of [11].
In the proof of the next proposition and several times in the remainder of the paper we use the following simple observation. Suppose that H is a balanced subgraph of G and F is a cellular face of G such that H contains all but one of the edges of ∂F . Then H ∪ ∂F is also balanced since adding the remaining edge cannot separate the ends of A.
Proposition 10.6. Suppose that G is a (2, 3, l)-tight A-graph that has at least one triangular face. Then G has a triangular face T and an edge e ∈ ∂T such that G e,T is (2, 3, l)-tight.
Proof. By Theorem 10.1 we can assume that G is unbalanced. Suppose that S is a triangular face and that G e,S is not (2, 3, l)-sparse for all e ∈ ∂S. Let B 1 , respectively B 2 , be blockers for two of the possible contractions of S. It is clear that . If both B 1 and B 2 are unbalanced then, by Lemma 9.3 or Lemma 9.4, B 1 ∪ B 2 is tight and unbalanced and so must be an induced subgraph of G which is a contradiction. Thus we can conclude that there is some edge f ∈ ∂S such that any blocker for G f,S is balanced. Let B be a maximal blocker for G f,S . So B is a balanced (2, 3, l)-tight graph. Let U be the face of B that contains the ends of A. By Lemma 10.5, and since G is unbalanced, we see that U contains S and that all the cellular faces of B are also faces of G. Let u be a vertex incident to f . Using Theorem 10.1, there is a triangular face T of B and e ∈ ∂T such that e is not incident to u and B e,T is (2, 3, l)-tight. Since T is a cellular face of B, it is also a face of G.
We will show that G e,T is (2, 3, l)-sparse. Suppose that C is a blocker for G e,T . By Lemma 9.3 or Lemma 9.4 we see that both B ∪ C and B ∩ C are (2, 3, l)-tight. Now B e,T is (2, 3, l)-sparse and therefore B ∩ C cannot be a blocker for this contraction. It follows that B ∩ C = {e} and in particular u ∈ V (C).
Suppose, seeking a contradiction, that E(C) ∩ E(∂S) is nonempty. Clearly f ∈ E(C) since C does not contain u. Therefore B ∪ C contains two of the edges of ∂S and (as observed above) it follows that B ∪ C ∪ ∂S is balanced if and only if B ∪ C is balanced. But B ∪ C is (2, 3, l)-tight, so B ∪ C ∪ ∂S = B ∪ C. Thus C must contain two of the edges of ∂S and hence u ∈ V (C) contradicting our earlier deduction. Thus E(C) ∩ E(∂S) = ∅ and so B ∪ C is a blocker for G f,S . By the maximality of B, we have C ⊂ B and hence C = B ∩ C = {e} which contradicts our choice of C as a blocker for G e,T .

Quadrilaterals
As previously noted, Proposition 10.6 is not sufficient to give a useful inductive characterisation of (2, 3, l)-tight A-graphs since there are infinitely many pairwise non-isomorphic examples that have no triangular faces.
For the rest of this section suppose that Q is a quadrilateral face of G with boundary walk v 1 , e 1 , v 2 , e 2 , v 3 , e 3 , v 4 , e 4 , v 1 . Note that we make no assumptions regarding the non-degeneracy of Q. Any such assumption will be explicitly stated as needed.
In contrast with the case of triangles, for quadrilateral contractions there are sufficiently many differences between the cases l = 1 and l = 2 to warrant separate treatments.

l = 2
Lemma 10.7. Suppose that G is a (2, 3, 2)-sparse A-graph and that Q is a degenerate quadrilateral face of G. Then Q is isomorphic to the A-graph shown in Figure  14  Then v is a cutvertex of G.
The situation with blockers for quadrilateral contractions is a little more complicated than for triangle contractions.  Note that a balanced type 3 blocker cannot arise in the context of (2, 3, 1)-sparsity. On the other hand, a disconnected type 3 blocker cannot arise in the context of (2, 3, 2)sparsity.
We refer to the graph B whose existence is asserted by Lemma 10.9 as type 1/2/3 blocker according to whichever case of the lemma applies. Note that for a given blocker B exactly one of (1)-(3) is true. See Figure 15 for some schematic diagrams indicating the topological embedding of various types of blockers. Note that these diagrams and those in Figures 16 and 18 are meant only as aids to the topological intuition of the reader. We do not rely on the faithfulness of any of these diagrams for the proofs in this section. We collect some observations about the blockers in the following lemmas. Proof. This follows easily using Equation (2) and the (2, 3, 2)-sparsity of G. Lemma 10.11. Suppose that B is a blocker of type 2 or 3 for G v 1 ,v 3 ,Q . Then V (B) separates v 2 and v 4 in G.
Proof. Consider the surface graph G ∪ δ where δ is a new edge embedded as a diagonal of Q joining v 1 and v 3 . Since B is connected by Lemma 10.10, we can find a cycle C in B ∪ δ that contains the edge δ. Since A has genus zero it follows that |C| is a loop that separates v 2 from v 4 in the surface. In particular any path in G from v 2 to v 4 must pass through some vertex of C. But V (C) ⊂ V (B).
Proposition 10.12. Suppose that G is a (2, 3, 2)-sparse A-graph and that Q is a quadrilateral face of G with boundary vertices Proof. Note that we proved that v 2 = v 4 in Lemma 10.9, so G v 2 ,v 4 ,Q is well defined. Now suppose that G v 2 ,v 4 ,Q is not (2, 3, 2)-sparse. Then by Lemma 10.9 there are blockers B 1 , respectively B 2 , for the contractions where d is the number of edges of ∂Q that are not in B 1 ∪ B 2 . In fact d = 1, 2 or 4 depending in an obvious way on the types of B 1 and B 2 . Now there are six cases to consider depending on the types of the respective blockers. We will derive a contradiction in each of these. In the following list "Case (X, Y )" means that B 1 is a type X blocker and B 2 is a type Y blocker. Note that, by Lemmas 10.10 and 10.11, B 1 ∩ B 2 is nonempty in all cases. Case (1, 1) : In this case d = 1. First observe that B 1 ∪ B 2 ∪ ∂Q is balanced if and only if B 1 ∪ B 2 is balanced. Now B 1 ∩ B 2 contains an edge of ∂Q, so by Lemma 9.3 B 1 ∪ B 2 is (2, 3, 2)-tight. Thus (6) yields the required contradiction.
Case (1,2): Without loss of generality suppose v 2 ∈ B 1 . In this case d = 2 so using (6) we have Now since B 1 is tight we have f (B 1 ) ≤ 3. It follows from (7) Figure 16 for an illustration. Now C is balanced since B 2 ∪ ∂Q is balanced. It follows that at least one of B or B is balanced, contradicting our earlier deduction.
Case (1,3): In this case d = 2 so (6) But since B 1 is (2, 3, 2)-tight it follows that B 1 must be balanced, and in fact f (B 1 ∩ B 2 ) = 2. Therefore B 1 ∩ B 2 must be a single vertex, which by Lemma 10.11 is a cutvertex for B 1 . However, we have shown that B 1 is balanced and so is a Laman graph, which cannot have a cutvertex.
Case (2,2): In this case, d = 4 and using (6) is a single vertex, say w, and that f (B 1 ∪ B 2 ∪ ∂Q) = 2. Now by Lemma 10.11, w is a cutvertex for both B 1 and B 2 .
, v 3 ∈ B and both B and B are Laman graphs and thus connected. Since B 2 ∪ ∂Q is balanced it has a face U that contains both ends of A. It is clear that one of B , B , without loss of generality say B , is disjoint from U . Therefore  It is worth noting that analogues of Proposition 10.12 fail for other similar classes of graphs. For example there are many examples of (2, 2)-tight torus graphs with quadrilateral faces for which both contractions yield graphs that are not (2, 2)-sparse. See [8] for details of this.

l = 1
In this subsection G will be a (2, 3, 1)-sparse A-graph. The general pattern of the arguments is similar to the (2, 3, 2)-sparse case. However, there are significant differences in the details of the statements and proofs, mostly due to the fact that if H is a balanced (2, 3, 1)-tight subgraph of G then the induced subgraph G(H) need not be (2, 3, 1)-tight. This complicates some of the discussion since we cannot assume that a blocker is an induced subgraph and so it cannot be characterised by its set of vertices. See Figure 17 for some examples. Figure 17: All three of these A-graphs are (2, 3, 1)-sparse. The graph on the left has a blocker for a triangle contraction that is not an induced subgraph. Likewise one of the contractions of the quadrilateral face of the middle graph has a blocker that is not induced. The quadrilateral face in the right hand graph has a blocker for one of its contractions that is not connected.
Also note that there are some additional degeneracies possible in the boundary of a quadrilateral face of a (2, 3, 1)-sparse A-graph.
Lemma 10.13. Suppose that Q is a degenerate quadrilateral face of a (2, 3, 1)-sparse A-graph G. Then ∂Q is isomorphic to one of the three A-graphs shown in Figure  14.
Proof. If ∂Q has no loop edges then as in the proof of Lemma 10.7 we can show that ∂Q is isomorphic to Figure 14(a). On the other hand, if ∂Q has a loop edge then such an edge must span an unbalanced subgraph and it is easy to see then that ∂Q must be isomorphic to (b) or (c) in Figure 14.
As before we will assume in the discussion below that the boundary walk of a quadrilateral Q is v 1 , e 1 , v 2 , e 2 , v 3 , e 3 , v 4 , e 4 , v 1 . We note with respect to the examples in Figure 14 that (b) and (c) satisfy v 1 = v 3 and v 2 = v 4 . In particular both G v 1 ,v 3 ,Q and G v 2 ,v 4 ,Q are defined in those cases. Note that even in these degenerate cases we still delete one vertex and two edges in the construction of the contracted graph. Let δ be a Jordan arc joining v 1 and v 3 whose interior lies in Q. We can think of δ as an edge that can be added to subgraphs of G.
Lemma 10.14. Suppose that G is a (2, 3, 1)-sparse A-graph, Q is a quadrilateral face of G with v 1 = v 3 and G v 1 ,v 3 ,Q is not (2, 3, 1)-sparse. Then at least one of the following statements is true.
(2) There is some subgraph B of G such that B contains at least one edge, f (B) ≤ 4, be the edge corresponding to {e 1 , e 2 } and let e ∈ E(G v 1 ,v 3 ,Q ) be the edge corresponding to {e 3 , e 4 }. Let A be a subgraph of G v 1 ,v 3 ,Q that violates the (2, 3, 1)sparsity count and choose A to be unbalanced if possible. Clearly z ∈ V (A) and |E(A) ∩ {e , e }| ≤ 1, otherwise G would also have a subgraph that violates the (2, 3, 1)-sparsity count. As pointed out above, if A is balanced we cannot assume that it is an induced subgraph. On the other hand, if A is unbalanced then we can and do assume that it is induced. Let B be the subgraph defined as follows. Let  (3) is true. On the other hand if A is balanced, then as observed above B ∪ δ is balanced. Moreover A has at least one edge and f (A) ≤ 2 so (2) is true.
We call the subgraph B whose existence is asserted by Lemma 10.14 a blocker for the contraction G v 1 ,v 3 ,Q . We call B a type 1/2/3 blocker according to which case of Lemma 10.14 applies. Again the diagrams in Figure 15 serve as guides for the intuition regarding the topology of the various types of blocker.
Lemma 10.15. If B is a type 1 or type 2 blocker for G v 1 ,v 3 ,Q then B is connected. If B is a type 3 blocker then either B is connected or it has precisely two components both of which are unbalanced and (2, 3, 1)-tight.
Proof. Using Equation (2) and the (2, 3, 1)-sparsity of G we see that if f (B) = 1 then B is connected. Similarly if f (B) ≤ 4 and B is balanced and disconnected then B has no edges. Finally if f (B) = 2 and B is disconnected then clearly, again using Equation (2), both components are unbalanced and (2, 3, 1)-tight.
See Figure 17 for an example of a disconnected type 3 blocker. vertices. If B 1 ∩B 2 is connected then it is easy to see that B 1 ∩(B 2 ∪∂Q) is connected and so B 1 ∪ B 2 ∪ ∂Q is balanced if and only if B 1 is balanced. Then we can proceed, mutatis mutandis, as in case (1, 2) of Proposition 10.12.
If B 1 ∩ B 2 is not connected then, since it is balanced, f (B 1 ∩ B 2 ) ≥ 4. Now using (10), and since B 1 is (2, 3, 1)-tight, we see that B 1 must be balanced, B 1 ∩B 2 = {u, v} consists of two isolated vertices and B 1 ∪B 2 ∪∂Q is unbalanced. Let δ be the diagonal of Q joining v 2 and v 4 . As in the proof of Lemma 10.11 there is a cycle C ⊂ B 2 ∪ δ such that δ ∈ E(C) and |C| separatese 1 ∪e 4 frome 2 ∪e 3 in A. Let F , F be the two faces of C and let B , respectively B , be the subgraph of B 1 that is disjoint from F , respectively F . Say Now C is a balanced cycle since B 2 ∪ δ is balanced, so without loss of generality, suppose that F is the face of C that contains both ends of A. Then C ∪ B is balanced and it follows easily that B 2 ∪ δ ∪ B is balanced. See Figure 18 for a schematic diagram of this situation. Now B 1 ∪ B 2 ∪ δ = B 1 ∪ (B 2 ∪ δ ∪ B ) and B 1 ∩ (B 2 ∪ δ ∪ B ) = B which is connected. Since B 1 and B 2 ∪δ ∪B are both balanced and B is connected, it follows from Lemma 9.1 that B 1 ∪ B 2 ∪ δ is balanced. It follows easily that B 1 ∪ B 2 ∪ ∂Q is balanced, contradicting our earlier deduction.
Case (1,3): In this case d = 2 so (9) yields Now B 1 is (2, 3, 1)-tight and B 1 ∩B 2 is not empty by Lemma 10.17, so it follows that B 1 is balanced and f (B 1 ∩ B 2 ) ≤ 2. Since B 1 ∩ B 2 is balanced, we conclude that B 1 ∩ B 2 is a single vertex, which without loss of generality we assume to be v 2 . If v 2 and v 4 are in the same component of B 2 then by Lemma 10.17, v 2 is a cutvertex for B 1 which contradicts the fact that B 1 is a Laman graph. On the other hand if v 2 and v 4 are in different components of B 2 then B 2 ∪ ∂Q must be embedded as shown in Figure 15. Since B 1 is balanced it is clear that v 2 must separate v 1 and v 3 in B 1 again contradicting the fact that B 1 is Laman. Case (2,2): In this case, d = 4 and using (9) we have f ( Let δ be the diagonal of Q joining v 1 and v 3 . By assumption B 1 ∪ δ is balanced and B 2 is also balanced. Now (B 1 ∪ δ) ∩ B 2 = B 1 ∩ B 2 which must be connected since f (B 1 ∩ B 2 ) ≤ 3. So by Lemma 9.1, B 1 ∪ B 2 ∪ δ is balanced. Let F be the face of B 1 ∪ B 2 ∪ δ that contains the ends of A.
By Lemma 10.17 there is a cycle C ⊂ B 1 ∪ δ that separatese 1 ∪e 2 frome 3 ∪e 4 . Now C is balanced since B 1 ∪ δ is balanced, so without loss of generality we can assume thate 1 ∪e 2 lies in a face of C that does not contain any of the ends of A. Since C ⊂ B 1 ∪B 2 ∪δ it follows thate 1 ∪e 2 ∩F = ∅. Therefore (B 1 ∪B 2 ∪δ)∪{e 1 , e 2 } is balanced. In particular B 1 ∪ B 2 ∪ {e 1 , e 2 } is balanced. Now by a similar argument (using the other diagonal of Q) we show that B 1 ∪ B 2 ∪ {e 2 , e 3 } is balanced. It follows, since B 1 ∪ B 2 ∪ e 2 is connected, that B 1 ∪ B 2 ∪ {e 1 , e 3 , e 3 } is balanced and then easily that B 1 ∪ B 2 ∪ ∂Q is balanced, contradicting our earlier deduction.
Case ( First observe that if |V (G)| ≤ 2 then G is isomorphic to K if it is balanced and L in the case l = 2, or M in the case l = 1, if it is unbalanced. Suppose that G has at least three vertices. If G is balanced then by Lemma 10.2 it has a triangular face. Now by Proposition 10.6, G e,T is (2, 3, l)-tight for some triangular face T and e ∈ ∂T . Moreover, it is clear that G e,T is also balanced. The conclusion follows by induction.
On the other hand, if G is unbalanced then by Lemma 10.2, either it has a triangular face or a quadrilateral face. Now by Propositions 10.6 and either Proposition 10.12 or Proposition 10.18 there is some contraction of G that is also (2, 3, l)-tight. Again the required conclusion follows by induction.

Completing sparse surface graphs to tight graphs
Finally we consider the problem of adding edges to a sparse surface graph to make it a tight surface graph. We begin with the case of a (2, 3)-sparse Σ-graph, where Σ is a connected surface. is (2, 3, 1)-tight and so e ∈ E(C) if f ∈ C. However, by Lemma 9.4 it would follow, in that case, that B ∪ C is (2, 3, 1)-tight contradicting the maximality of B (since f ∈ B). Thus we have shown that f ∈ E(C). Now suppose, seeking a contradiction, that B is unbalanced. Then w ∈ B and so B ∪ C is not (2, 3, 1)-tight. By Lemma 9.4 it follows that B ∩ C = {v} and that C is balanced. Since e, f, ∈ E(C) it follows that C ∪ {u, e, f } is a (2, 3, 1)tight subgraph of G (which is unbalanced if and only if u = v). By Lemma 9.4, B ∪ (C ∪ {u, e, f }) = B ∪ C ∪ f is (2, 3, 1)-tight, contradicting the maximality of B.
Thus we can assume that B is balanced. Now suppose, seeking a contradiction, that C ⊂ B. Then C is balanced and so C ∪ δ is also balanced. Thus B ∪ δ = B ∪ (C ∪ δ) is also balanced, using Lemma 9.1. Since κ bounds a triangle, it follows that B ∪ δ ∪ f is balanced. But then, since B is tight, we have f ∈ E(B), contradicting our earlier deduction.
Thus C ⊂ B and so B ∪ C is not (2, 3, 1)-tight. It follows from Lemma 9.4 that B ∩ C has no edges and at most two vertices. If |V (B ∩ C)| = 2 then B ∪ C ∪ f is unbalanced and (2, 3, 1)-tight, contradicting the maximality of B. If |V (B ∩ C)| = 1 then Again we conclude that B ∪ C ∪ f is (2, 3, 1)-tight, contradicting the maximality of B.