Planar graphs as L-intersection or L-contact graphs
Daniel Gonçalves Lucas Isenmann Claire Pennarun
cs.CG


Time irreversibility and multifractality of power along single particle trajectories in turbulence[Version accepted for publication (postprint) on Phys. Rev. Fluids 2, 104604 – Published 27 October 2017]
    Massimo De Pietro
    
===========================================================================================================================================================================================================







  The ⌞-intersection graphs are the graphs that have a representation as intersection graphs of axis parallel ⌞ shapes in the plane. A subfamily of
  these graphs are {⌞,| ,- }-contact graphs which
  are the contact graphs of axis parallel ⌞, |, and - shapes
  in the plane. We prove here two results that were
  conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs
  are ⌞-intersection graphs, and that triangle-free
  planar graphs are {⌞,| ,- }-contact graphs. 
  These results are 
  
  
  obtained by a new and simple decomposition technique for 4-connected triangulations. 
  Our results also provide a much simpler proof of the known fact that planar 
  graphs are segment intersection graphs.

 



§ INTRODUCTION


The representation of graphs by contact or intersection of predefined shapes in the plane is a broad subject of research since the work of Koebe on the representation of planar graphs by contacts of circles <cit.>.
In particular, the class of planar graphs has been widely studied in this context.

More formally, assigning a shape X of the plane for each vertex of a graph G, we say that G is a X-intersection graph if there is a representation of G such that every vertex is assigned to a shape X, and two shapes X_1, X_2 intersect if and only if the vertices they are assigned to are adjacent in G.
In the case where the shape X is homeomorphic to segments (resp. discs), a X-contact system is a collection of X shapes such that if an intersection occurs between two shapes, then it occurs at one of their endpoints (resp. on their border).
We say that a graph G is a X-contact graph if it is the intersection graph of a X-contact system.
This definition can be easily generalized if the representation of each vertex is chosen among a family of shapes.

The case of shapes that are homeomorphic to a disc has been widely studied; see for example the literature for triangles <cit.>, homothetic triangles <cit.>, axis parallel rectangles <cit.>, squares <cit.>, hexagons <cit.>, or convex bodies <cit.>.
We here focus on the representation of planar graphs as contact or intersection graphs, where the assigned shapes are segments or polylines in the plane.
The simplest definition of representation of graphs by intersection of curves is the so-called string-representation: each vertex is represented by a curve, and two curves intersect if and only if the vertices they represent are adjacent in the graph. It is known that every planar graph has a string-representation <cit.>. 
However, this representation may contain pairs of curves that cross any number of times. One may thus take an additional parameter into account, namely the maximal number of crossings of any two of the curves: a 1-string representation of a graph is a string representation where every two curves intersect at most once. The question of finding a 1-string representation of planar graphs has been solved by Chalopin et al. in the positive <cit.>, and additional parameters are now studied, like order-preserving representations <cit.>.

Segment intersection graphs are in turn a specialization of the class of 1-string graphs. It is known that bipartite planar graphs are {|,-}-contact graphs <cit.> (i.e. segment contact graphs with vertical or horizontal segments). 
De Castro et al. <cit.> showed that triangle-free planar graphs are segment contact graphs with only three different slopes. De Fraysseix and Ossona de Mendez <cit.> then proved that a larger class of planar graphs are segment intersection graphs.
Finally, Chalopin and the first author extended this result to general planar graphs <cit.>, which was conjectured by Scheinerman in his PhD thesis <cit.>.

A graph is said to be a VPG-graph (Vertex-Path-Grid) if it has a contact or intersection representation in which each vertex is a path of vertical and horizontal segments (see <cit.>). Asinowski et al. <cit.> showed that the class of VPG-graphs is equivalent to the class of graphs admitting a string-representation. They also defined the class B_k-VPG, which contains all VPG-graphs for which each vertex is represented by a path with at most k bends (see <cit.> for the determination of the value of k for some classes of graphs).
It is known that B_k-VPG ⊈ B_k+1-VPG, and that the recognition of graphs of B_k-VPG is an NP-complete problem <cit.>.
These classes have interesting algorithmic properties (see for example <cit.> for approximation algorithms for independence and domination problems in B_1-VPG graphs), but most of the literature studies their combinatorial properties.

Chaplick et al. <cit.> proved that planar graphs are B_2-VPG graphs. This result was recently improved by Biedl and Derka <cit.>, as they showed that planar graphs have a 1-string B_2-VPG representation.

Various classes of graphs have been showed to have 1-string B_1-VPG representations, such as planar partial 3-trees <cit.> and Halin graphs <cit.>. Interestingly, it has been showed that the class of segment contact graphs is equivalent to the one of B_1-VPG contact graphs <cit.>. This implies in particular that triangle-free planar graphs are B_1-VPG contact graphs. This has been improved by Chaplick et al. <cit.> as they showed that triangle-free planar graphs are in fact {⌞, ⌜, |, -}-contact graphs (that is without using the shapes ⌟ and ⌝).

The restriction of B_1-VPG to ⌞-intersection or ⌞-contact graphs has been much studied (see for example <cit.>) and it has been shown that they are in relation with other structures such as Schnyder realizers, canonical orders or edge labelings <cit.>. 
The same authors also proved that the recognition of ⌞-contact graphs can be done in quadratic time, and that this class is equivalent to the one restricted to equilateral ⌞ shapes. Finally, the monotone (or linear) ⌞-contact graphs have been recently studied further, for example in relation with MPT (Max-Point Tolerance) graphs <cit.>.





  
Our contributions

The two main results of this paper are the following:


    
  Every triangle-free planar graph is a {⌞, | , -}-contact graph.



    
  Every planar graph is a ⌞-intersection graph.


Both results were conjectured in  <cit.>. Theorem <ref> is optimal in the sense that a {⌞, | , -}-contact graph with n vertices has at most 2n-3 edges, while triangle-free planar graphs may have up to 2n-4 edges. However, up to our knowledge, the question of whether every triangle-free planar graph is a {⌞, | }-contact graph is open [In fact, it has been proven in the Masters thesis (in German) of Björn Kapelle in 2015 <cit.>, but never published.].
Theorem <ref> implies that planar graphs are in B_1-VPG, improving the results of Biedl and Derka <cit.> stating that planar graphs are in B_2-VPG.
Since a ⌞-intersection representation can be turned into a
segment intersection representation <cit.>, this also directly provides a rather simple proof of the fact that planar graphs are segment intersection graphs <cit.>.
Note that a simple modification of our method can be used to prove that 4-connected planar graphs have a B_3-EPG representation <cit.>, where vertices are represented by paths on a rectangular grid with at most 3 bends, and adjacency is shown by sharing an edge of the grid.

The common ingredient of the two results is what we call 2-sided near-triangulations.
In Section <ref>, we present the 2-sided near-triangulations, allowing us to provide a new decomposition of planar 4-connected triangulations (see <cit.> and <cit.> for other decompositions of 4-connected triangulations). This decomposition is simpler than the one provided by Whitney <cit.> that is used in <cit.>.
In Section <ref>, we define thick ⌞-contact systems, (i.e., ⌞-contact representations in which the shapes have some thickness ε)  with specific properties. We then show that every 2-sided near-triangulation can be represented by such a system. This result is used in Section <ref> to prove Theorem 1. Then in Section <ref> we use 2-sided near-triangulations to prove Theorem 2.



§ 2-SIDED NEAR-TRIANGULATIONS


In this paper we consider plane graphs without loops nor multiple
edges. In a plane graph there is an infinite face, called the outer face, and the other faces are called inner faces. 
A near-triangulation is a 
plane graph such that every inner face is a triangle. 
In a plane graph G, a chord is an edge not incident to the outer face but that links two vertices of the outer face.
A separating triangle of G is a cycle of length three such that both regions delimited by this cycle (the inner and the outer region)
contain some vertices. 
It is well known that a triangulation is
4-connected if and only if it contains no separating triangle.
Given a vertex v on the outer face, the inner-neighbors of v are the neighbors of v that are not on the outer face.
We define here 2-sided near-triangulations (see Figure <ref>) whose structure will be useful in the inductions of the proofs of Theorem <ref>, and Theorem <ref>.


  A 2-sided near-triangulation is a 2-connected near-triangulation T without
  separating triangle and such that going clockwise on its
  outer face, the vertices are denoted a_1,a_2,…, a_p, b_q,
  …, b_2,b_1, with p≥ 1 and q≥ 1, and such that there is
  no chord a_ia_j or b_ib_j (that is an edge a_ia_j or b_ib_j
  such that |i-j| > 1).




The structure of the 2-sided near-triangulations allows us to describe the following decomposition:

 
  Given a 2-sided near-triangulation T with at least 4 vertices, one can always perform one of the
  following operations:
  
  
  (a_p-removal) This operation applies if p>1, if a_p has
    no neighbor b_i with i<q, and if none of the inner-neighbors
    of a_p has a neighbor b_i with i<q. This operation consists
    in removing a_p from T, and in denoting b_q+1, …,
    b_q+r in anti-clockwise order the new vertices on the outer face, if any. This
    yields a 2-sided near-triangulation T' (see Figure <ref>).
    
  
  (b_q-removal) This operation applies if q>1, if b_q has
    no neighbor a_i with i<p, and if none of the inner-neighbors
    of b_q has a neighbor a_i with i<p. This operation consists
    in removing b_q from T, and in denoting a_p+1, …,
    a_p+r in clockwise order the new vertices on the outer face, if any. This
    yields a 2-sided near-triangulation T'. 
    This operation is strictly symmetric to the previous one.
    
  
  (cutting) This operation applies if p> 1 and q>1, and if the
    unique common neighbor of a_p and b_q, denoted x, has a
    neighbor a_i with i<p, and a neighbor b_j with j<q. If x
    has several such neighbors, i and j correspond to the smaller
    possible values. This operation consists in cutting T into three
    2-sided near-triangulations T', T_a and T_b
(see Figure <ref>):
    
    
  * T' is the 2-sided near-triangulation
    contained in the cycle formed by vertices (a_1,…,a_i,x,b_j,…,b_1), and the vertex x is renamed a_i+1.
    
  * T_a
    (resp. T_b) is the 2-sided near-triangulation contained in the cycle
    (a_i,…,a_p,x) (resp. (x,b_q,…,b_j)), where the
    vertex x is denoted b_1 (resp. a_1).
    
    
  







Suppose that a_p has no neighbor b_i with i < q and none of the
inner-neighbors of a_p has a neighbor b_i with i < q.
We denote b_q+1, … , b_q+r the inner-neighbors of a_p in anti-clockwise order
such that b_j is connected to b_j+1 for every q ≤ j ≤ r.
Let T' be the graph obtained by removing a_p and its adjacent edges from T.
It is clear that T' is a near-triangulation, and that it has no separating triangle (otherwise T would have one too). Furthermore, as there is no chord incident to a_p, and as T' has at least three vertices its outer face is bounded by a cycle, and T' is thus 2-connected. 
As T is a 2-sided near-triangulation, T' has no chord a_i a_j, with i,j< p, or b_i b_j with i,j ≤ q.
By hypothesis, the inner-neighbors of a_p have no neighbors
b_k with k < q, thus there is no chord b_i b_j with i ≤ q and
q < j. There is no chord b_i b_j in T' with q ≤ i < j. 
Otherwise the vertices a_p, b_i, and b_j would form a triangle with at least one vertex inside, b_i+1, and at least one vertex outside, a_p-1: it would be a separating triangle, a contradiction.
Therefore T' is a 2-sided near-triangulation.

The proof for the b_q-removal operation is analogous to the previous
case.

Suppose that we are not in the first case nor in the second one.
Let us first show that p>1 and q>1. Towards a contradiction, consider that p=1. Then as T is 2-connected, it has at least three vertices on the outer face and q≥ 2. In such a case one can always perform the b_q-removal operation, a contradiction.

Let us now show that a_p is not adjacent to a vertex b_i with i<q. Towards a contradiction, consider that a_p is adjacent to a vertex b_i with i<q. Then by planarity, b_q (with q>1) has no neighbor a_i with i<p, and has no inner-neighbor adjacent to a vertex a_i with i<p. In such a case one can always perform the b_q-removal operation, a contradiction. Symmetrically, we deduce that b_q is not adjacent to a vertex a_i with i<p.

Vertices a_p and b_q have one common neighbor x such that xa_pb_q is an inner face. Note that as there is no chord incident to a_p or b_q, then x is not on the outer face. They have no other common neighbor y, otherwise there would be a separating triangle ya_pb_q (separating x from both vertices a_1 and b_1). 

As we are not in the first case nor in the second case, we have that a_p (resp. b_q) has (at least) one inner-neighbor adjacent to a vertex b_i with i<q (resp. a_i with i<p). By planarity, x is the only inner-neighbor of a_p (resp. b_q) adjacent to a vertex b_i with i<q (resp. a_i with i<p). We can thus apply the cutting operation.

We now show that T', T_a and T_b are 2-sided near-triangulations.
Consider first T'.
It is clear that it is a near-triangulation without separating triangles.
It remains to show that there are no chords a_ia_j or b_ib_j. By definition of T', the only chord possible would have x=a_i+1 as an endpoint, but the existence of an edge xa_k with k<i would contradict the minimality of i.
Thus T' is a 2-sided near-triangulation.

By definition, T_a is also a near-triangulation containing no separating triangles.
Moreover, there is no chord a_k a_l with i ≤ k ≤ l-2 as there are no such chords in T.
Therefore T_a is a 2-sided near-triangulation.
We show in the same way that T_b is a 2-sided near-triangulation.





§ THICK {⌞}-CONTACT SYSTEM




A  is a ⌞ shape where the two
segments are turned into ε-thick rectangles (see
Figure <ref>).
Going clockwise around a thick ⌞ from the bottom-right corner, we call its sides
bottom, left, top, vertical
  interior, horizontal interior, and right.
  

A  is described by four coordinates a,b,c,d such that a+ε < b and c+ε < d. It is thus the union of two boxes: ([a,a+ε] × [c,d]) ∪ ([a,b] × [c,c+ε]). If not specified, the corner of a  denotes its bottom-left corner (with coordinate (a,c)). In the rest of the paper, all the  shapes have the same thickness ε.



Given a -contact system, a thick ⌞ is said left if its horizontal interior is free (i.e., does not touch another ⌞) and its left side is not contained in the side of another thick ⌞  (see Figure <ref>). Similarly, a thick ⌞ is said bottom if its vertical interior is free and its bottom side is not contained in the side of another thick ⌞ (see Figure <ref>).






    A convenient -contact system (CTLCS) is a contact
    system with  shapes (which implies that the  shapes
    interiors are disjoint) with a few properties:
    
    
    
  * Two  shapes intersect either on exactly one segment or on a
      point (Figure <ref> lists the allowed ways two
      ⌞ shapes can intersect). If the intersection is a segment, then it must be exactly one side of a . If the intersection is a point, then it is the bottom right corner of one  and the top left corner of the other one.
    
  * Every thick ⌞ is bottom or left.
    




Remark that the removal of any  still leads to a CTLCS.
This definition implies that in a CTLCS there is no three ⌞ shapes intersecting as in Figure <ref>.



We now make a link between CTLCS and 2-sided near-triangulations (See Figure <ref> for an illustration).

 
  Every 2-sided near-triangulation can be represented by a CTLCS with the following properties:
      
      
  * every  is included in the quadrant { (x,y) : x≥ 0, y ≥ 0 },
      
  * a_1 has the rightmost corner and b_1 has the up-most corner,
      
  * every vertex a_i is represented by a bottom  whose corner has
        coordinates (x,0), with x>0, and
      
  * every vertex b_i is represented by a left  whose corner has
        coordinates (0,y), with y>0.
      





We proceed by induction on the number of vertices.
The theorem clearly holds for the 2-sided near-triangulation with three
vertices. 
Let T be a 2-sided near-triangulation; it can thus be decomposed using one of the three operations described in Lemma <ref>. We go through the three operations successively.

(a_p-removal) 
Let T' be the 2-sided near-triangulation resulting from an a_p-removal operation on T. By the induction hypothesis, T' has a CTLCS with the required properties (see Figure <ref>).
We can now modify this CTLCS slightly in order to obtain a CTLCS of T (thus adding a  corresponding to vertex a_p).
Move the corners of the  corresponding to vertices
b_q+1,…, b_q+r slightly to the right. Since these are left  shapes, one can do this without modifying the rest of the system.
Then one can add the  of a_p such that it touches the  of vertices b_q and a_p-1 (as depicted
in Figure <ref>). One can easily check that the obtained
system is a CTLCS of T and satisfies all the requirements.



(b_q-removal) This case is strictly symmetric to the previous one.

(cutting) Let T', T_a and T_b be the three 2-sided near-triangulations resulting from the cutting operation described in Lemma <ref>. By induction hypothesis, each of them has a CTLCS satisfying the requirements of Theorem <ref>.
Consider the CTLCS of T' (see Figure <ref>). Move
the corner of x=a_i+1 slightly upward. Since x=a_i+1 is a bottom
vertex, one can do this without modifying the rest of the system. 
Then one can add the CTLCS of T_a below vertex x and the one of T_b on its left (see Figure <ref>, bottom). One can easily check that the
obtained system satisfies all the requirements.




 
    
 
 
  
  
  
  
  
  
  
  
  
  
  
  
   
   
    
     
      
      
      
      
      
      
    
    
    

 





















  



§ {⌞,| ,- }-CONTACT SYSTEMS FOR TRIANGLE-FREE PLANAR GRAPHS



We can now use the CTLCS systems to prove Theorem <ref>. Recall that a 
{⌞,| ,-}-contact system is a contact system with some ⌞, some vertical segments |, and some horizontal segments -, such that if an intersection occurs between two of these objects, then the intersection is an endpoint of one of the two objects.
We need the following lemma as a tool (it is proved in appendix).

 
    For any plane triangle-free graph G, there exists a 4-connected triangulation T containing G as an induced subgraph.




  
We can now prove Theorem <ref>, which asserts that every triangle-free planar graph has a {⌞,| ,-}-contact system.


Consider a triangle-free planar graph G.
According to Lemma <ref>, there exists a
4-connected triangulation T containing G as an induced subgraph.
As the exterior face of T is a triangle, T is a 2-sided near-triangulation (denoting a_1,b_2,b_1 the three exterior vertices in clockwise order). 
By Theorem <ref>, T has a
CTLCS and removing every  corresponding to a 
vertex of T∖ G leads to a CTLCS of G. 



If a  x has its bottom side included in the horizontal interior side of another  y, then x is bottom, and so does not intersect anyone on its horizontal interior side. Furthermore, x does not intersect anyone on its right side nor on its bottom right corner. Indeed, if there was such an intersection with a  z, then y and z would also intersect, contradicting the fact that G is triangle-free (see Figure <ref>). One can thus replace the  of x by a thick |.



Similarly, if a  x has its left side included in the vertical interior side of a  y, we can replace the  of x by a thick -.

Note that now the intersections are on small segments, or on a point, between the bottom right corner of a  or -, and the top left corner of a  or |.
Then, we replace each thick ⌞, |, and - by thin ones as depicted in Figure <ref>. It is clear that we obtain a {⌞, |, -}-contact system whose contact graph is G. This concludes the proof.
An example of the process is shown in Figure <ref>.










§ THE ⌞-INTERSECTION SYSTEMS



An ⌞-intersection system (LIS) is an intersection system of ⌞ shapes where every two ⌞ shapes intersect on at most one point.
Using Theorem <ref>, one could prove that that every 4-connected triangulation has a LIS. To allow us to work on every triangulation (not only the 4-connected ones) we need to enrich our LISs with the following notion that was introduced in <cit.> under the name of private region.

An anchor can be seen as a union of three segments, or as the union of two ⌞. It has two corners, which correspond to the ⌞ shapes corners. There are two types of anchors.
A horizontal anchor is a set [x_1,x_3] × y_1 ∪ x_1 × [y_1,y_2] ∪ x_2 × [y_1,y_2] where x_1 < x_2 < x_3 and y_1 < y_2 (see Figure <ref>a).
The middle corner of such a horizontal anchor is defined as the point (x_2,y_1).
A vertical anchor is a set x_1 × [y_1,y_3] ∪ [x_1,x_2] × y_1 ∪ [x_1,x_2] × y_2 where x_1 < x_2 and y_1 < y_2 < y_3 (see Figure <ref>b).
The middle corner of such a vertical anchor is defined as the point (x_1,y_2).

Consider a near-triangulation T, and any inner face abc of T. Given a LIS of T, an anchor of abc is an anchor crossing the ⌞ shapes of a b and c and no other ⌞, and such that the middle corner is in the square described by a, b and c as depicted in Figure <ref>.




    A full ⌞-intersection system (FLIS) of a near-triangulation T is a LIS of T with an anchor for every (triangular) inner face of T, such that the anchors are pairwise non-intersecting.





Let us now prove that every 2-sided near-triangulation admits a FLIS.


 Every 2-sided near-triangulation has a FLIS such that among the corners of the ⌞ shapes and the anchors:


  * from left to right, the first corners are those of vertices b_1,b_2,… b_q and the last one is the corner of vertex a_1, and

  * from bottom to top, the first corners are those of vertices a_1,a_2,… a_p and the last one is the corner of vertex b_1.



As the ⌞ of a_i and a_i+1 (resp. b_i and b_i+1) intersect, the FLIS is rather constrained. This is illustrated in Figure <ref>, where the grey region contains the corners of the inner vertices, and the corners of the anchors.
  



We proceed by induction on the number of vertices.

The result clearly holds for the 2-sided near-triangulation with three
vertices, whatever p=1 and q=2, or p=2 and q=1. Let T be a 2-sided near-triangulation with at least four vertices.
By Lemma <ref> we consider one of the following operations on T:

(a_p-removal) Consider the FLIS of T' obtained by induction
and see in Figure <ref> how one can add a ⌞ for a_p and an anchor for each inner face a_pb_jb_j+1 with q≤ j <q+r and for the inner face a_p a_p-1 b_q+r. One can easily check that the obtained system verifies all the requirements of Proposition <ref>.





(b_q-removal) This case is symmetric to the previous one.

(cutting) Consider the FLISs of T', T_a and T_b. 
Figure <ref> depicts how to combine them, and how to add an anchor for xa_pb_q, in order to get the FLIS of T. One can easily check that the obtained system verifies all the requirements of Proposition <ref>.


We now prove Theorem <ref> which asserts that every planar graph is a  ⌞-intersection graph. 
It is well known that every planar graph is an induced subgraph of some triangulation (see <cit.> for a proof similar to the one of Lemma <ref>).
Thus, given a planar graph G, one can build a triangulation T whose G is an induced subgraph. If one can create a FLIS of T, then it remains to remove the ⌞ shapes assigned to vertices of T ∖ G along with the anchors in order to get a ⌞-representation of G.
In order to prove Theorem <ref>, we thus only need to show that every triangulation admits a FLIS. 




 
  Every triangulation T with outer-vertices x,y, z has a FLIS such that among the corners of the ⌞ shapes and the anchors:
  
  
  * the corner of x is the upmost and leftmost,
  
  * the corner of y is the second leftmost, and
  
  * the corner of z is the bottom-most and rightmost.
  






Note that in this proposition there is no constraint on x, y, z, so by renaming the outer vertices, other FLISs can be obtained. Another way to obtain more FLISs is by applying a reflection with respect to a line of slope 1. In such FLIS (see Figure <ref>) among the corners of the ⌞ shapes and the anchors:
  
  
  * the corner of x is the bottom-most and rightmost,
  
  * the corner of y is the second bottom-most, and
  
  * the corner of z is the upmost and leftmost.
   



We proceed by induction on the number of vertices in T.
Let T be a triangulation with outer vertices x,y,z.

If T is 4-connected, then it is also a 2-sided near-triangulation. By Proposition <ref> and by renaming the outer-vertices x to b_1, y to b_2 and z to a_1, T has a FLIS with the required properties. 

If T is not 4-connected, then it has a separating triangle formed by vertices a, b and c.
We note T_in and T_out the triangulations obtained from T by removing the vertices outside and inside abc respectively.

By the induction hypothesis, T_out has a FLIS verifying Proposition <ref> (considering the outer vertices to be x,y,z in the same order).
Without loss of generality we can suppose that the ⌞ shapes of a, b and c appear in the following order: the upmost and leftmost is b, the second leftmost is c and the bottom-most is a. There are two cases according to the type of the anchor of the inner face abc.

If the anchor of abc in the FLIS of T_out is vertical (see Figure <ref>), then applying the induction hypothesis on T_in with b,c,a as outer vertices considered in that order, T_in has a FLIS as depicted on the Figure <ref>.
Figure <ref> depicts how to include the FLIS of T_in∖{a,b,c} in the close neighborhood of the anchor of abc.
As abc is not a face of T, the close neighborhood of its anchor is indeed available for this operation.



Now suppose that the anchor of abc in the FLIS of T_out is horizontal (see Figure <ref>).
By application of the induction hypothesis on T_in with a,c,b as outer vertices considered in that order, then T_in has a FLIS as depicted on the Figure <ref>.
By a reflection of slope 1, T_in has a FLIS such that b is the up-most and left-most, c is the second left-most and a is bottom-most (see Figure <ref>).
Similarly to the previous case, we include this last FLIS of T_in∖{a,b,c} in the one from T_out (see Figure <ref>). As T_in and T_out cover T, and intersect only on the triangle abc, and as every inner face of T is an inner face in T_in or in T_out, these constructions clearly verify Proposition <ref>.
This concludes the proof of the proposition.































§ FROM TRIANGLE-FREE PLANAR GRAPHS TO 4-CONNECTED TRIANGULATIONS


We here prove Lemma <ref>.






The main idea of the construction of T is to insert vertices and edges in every face of G (even for the exterior face).

For the sake of clarity, vertices of G are said black and vertices of T ∖ G are said red. 
The new graph T contains G as an induced subgraph, along with other vertices and edges. More precisely, for every face of G, let P = {v_0,e_0,v_1,e_1,…} be the list of vertices and edges along the face boundary (see Figure <ref>), where e_i is the edge between vertices v_i and v_i+1; there can be repetitions of vertices or edges. 
For each face of G, given the list P, the graph T contains a vertex v'_i for each vertex v_i, a vertex e'_i for each edge e_i, and an additionnal vertex t.
Each vertex v'_i is connected to e'_i and e'_i+1 (with subscripts addition done modulo the size of the face), each vertex v_i is connected to v'_i, e'_i-1 and e'_i,
and the vertex t is connected to all vertices v'_i and e'_i (see Figures <ref> and <ref> for examples).




The new graph T is a triangulation, and we now show that it is 4-connected, i.e., has no separating triangle.
    Suppose that there is a separating triangle in the new graph. There are four cases depending on the colors of the edges of this triangle:
    
    
    
  * The separating triangle contains three black edges.
    It is impossible since G is triangle-free.
    
    
  * The separating triangle contains exactly one red edge.
    One of its endpoints must be a red vertex.
    But a red vertex is adjacent to only red edges, a contradiction.
    
    
  * The separating triangle contains exactly two red edges. Then their common endpoint is a red vertex, and the triangle is made of two vertices v_i and v_i+1, together with the vertex e'_i. All these triangles are faces, a contradiction. 
    
    
  * The separating triangle contains three red edges.
    Since for each face, the red vertices (vertices v'_i, e'_i and t) induce a wheel graph centered on t, with at least 8 peripheral vertices (vertices v'_i and e'_i), this separating triangle has at least one black vertex. As two adjacent black vertices are linked by a black edge, this separating triangle has exactly one black vertex. As the two red vertices are two adjacent v'_i or e'_j vertices, we have that those are v'_i and e'_j, for some i and for j=i or for j=i+1. Such a triangle is not separating, a contradiction.
    
    This concludes the proof of the lemma.




plain



