Triangle-Free Planar Graphs as Segment Intersection Graphs

Triangle-Free Planar Graphs as Segments Intersection Graphs N. de Castro1,F.J.Cobos 1, J.C. Dana1,A.M´arquez1, and M. Noy2 1Departamento de Matem´atica Aplicada I Universidad de Sevilla, Spain {natalia,cobos,dana,almar}@cica.es 2Dpto. de Matem´atica Aplicada II Universitat Polit`ecnica de Catalunya??? , Spain [email protected] Abstract. We prove that every triangle-free planar graph is the graph of intersection of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and oblique) and in such a way that no two segments cross, i.e., intersect in a common interior point. 1 Introduction Given a set Sof segments in the plane, its intersection graph has a vertex for every segment and two vertices are adjacent if the corresponding segments intersect. Intersection graphs of segments and other geometrical objects have been widely studied in the past. For instance, if the segments are contained in a straight line then we have the interval graphs [4], a well-known family of perfect graphs. If the segments are chords of a circle then the intersection graph is called a circle graph, see for instance [6,8]. In the general case, there is no satisfactory characterization, but some results are known for planar graphs. The most interesting one is due to de Fraysseix, Osona de Mendez and Pach [3], and independently to Ben-Arroyo Hartman, Newman and Ziv [2], which says that every planar bipartite graph is the intersection graph of a set of horizontal and vertical segments (on the other hand, it is known that the recognition of such graphs is an NP-complete problem [5]). This result provides a partial answer to a question of Scheinerman [7]: is every planar graph the intersection graph of a set of segments in the plane? The main result in this paper, which is a significant extension of [3], is that every triangle-free planar graph is the intersection graph of a family of segments. Moreover, the segments can be drawn in only three directions and in such a way that they do not cross. This particular class of intersection graphs is also known as contact graphs. We call such a representation a segment representation of the graph. ??? Partially supported by DGES-MEC-PB96-0005-C02 J. Kratochv´ıl (Ed.): GD’99, LNCS 1731, pp. 341–350, 1999. c Springer-Verlag Berlin Heidelberg 1999 342 N. de Castro et al. A key point in our proof is Gr¨otszch’s Theorem [9], which guarantees that every planar triangle-free graph is 3-colorable. The sketch of the proof is as follows. Given a triangle-free plane graph G, adding new vertices and (induced) paths between the vertices of Gwe can obtain a new triangle-free plane graph which is a subdivision of a 3-connected graph. Starting with a 3-coloring, a segment representation in three directions is obtained for this new graph using several technical lemmas. Finally, removing the dummy vertices and paths, we obtain a segment representation of the graph G. The three directions considered are horizontal, vertical and oblique (parallel to the bisector of the second quadrant of the plane). h1 h1 h2 h2 h3h4 h5 h5 h6 h6 h3 h4 v1 v1 v2 v2 v3 v3v4 v4v5 v5 v6 v7 v6 v7 o1 o1 o2 o2 o3 o3 Fig. 1. A segment representation of a planar graph. 2 Convex Faces with Three Directions Let IGbe a segment representation of a plane graph G.Asegment path of length nis a sequence of segments P={s1,...,s n}such that segment siis adjacent to si−1and si+1 for 1 <i<n. The representation IGdivides the plane into regions that we call faces of the representation and which correspond to the faces of G. A face Fof a segment representation is convex if its boundary can be divided into four paths (clockwise) P1,P2,P3and P4such that if sis a segment with extremes in the points (x1,y 1) and (x2,y 2) then: 1. if sis in P1, then x1<x 2if sis horizontal, y1>y 2if sis vertical and x1<x 2and y1>y 2if sis oblique; 2. if sis in P2, then x1>x 2if sis horizontal, y1>y 2if sis vertical and x1>x 2and y1<y 2if sis oblique; 3. if sis in P3, then x1>x 2if sis horizontal, y1<y 2if sis vertical and x1>x 2and y1<y 2if sis oblique; 4. if sis in P4, then x1<x 2if sis horizontal, y1<y 2if sis vertical and x1<x 2and y1>y 2if sis oblique. Triangle-Free Planar Graphs as Segments Intersection Graphs 343 It can be seen that the partition of a convex face into P1,P2,P3and P4is not unique, for instance in the example of Figure 2 the first segment of P1could be in P4. If the segments s1,...,s nare the intersection between two convex faces Fand G, we will assign those segments to only one path in each face, following the newt rule: if this segments belongs to P1in F, then they belongs to P3in G and reciprocally. Analogously if they belongs to P2in F, then they are in P4of Gand reciprocally. This rule alow us to fix the partition of a convex face into the four paths depending on the adjacent faces if the partition is not unique. F P1 2 3 4 P P P Convex Face Non Convex Face Fig. 2. The four paths of a convex face. Lemma 1. Let IGbe a segment representation of a plane graph Gsuch that all its faces are convex, let kbe a positive real number and let sbe a segment of length lin a face Fof IG. Then, IGcan be transformed into another segment representation I0 Gsatisfying: 1. IGand I0 Ghave the same faces and face boundaries as G, and the faces of I0 Gare convex; 2. the length of sin I0 Gis k+l; 3. at most two segments of F(other than s) have different length in IGand I0 G. Proof. Let P1,P2,P3and P4denote the paths which make Fconvex. Call the upper part (the lower part) of the face the union of the paths P4and P1(P2and P3, respectively). Similarly, the right part (the left part) is the union of the paths P1and P2(P3and P4, respectively). The proof is by induction on the number of faces of the graph G. Suppose that IGis just the cycle Fand let sbe the segment of Fwe want to enlarge. Without loss of generality we can suppose that sis a horizontal segment. If sis in the upper part of F, we seek another horizontal segment s0in the lower part of F. If there exists such a segment, we enlarge sand s0by the same amount and we make a translation of all the segments between sand s0, transforming Finto other convex face (see Figure 3). Otherwise, there must exist a vertical segment s0and an oblique segment s00 in the lower part of F, because the boundary of Fis a closed path. In this case, we increase the length of s,s0 and s00 and we make a translation of the rest of the segments (see Figure 3). 344 N. de Castro et al. According to the above remark, we suppose in the rest of the proof that there exists a segment parallel to sin the opposite part of F. Suppose now that IGhas two convex faces Fand F0sharing the segments s1,...,s n. First of all, by the convexity of Fand F0, observe that if s1,...,s n are segments of P1(P2), then s1,...,s nform part of P0 3(P0 4, respectively). Thus, suppose that s1,...,s nbelong to P1in Fand to P0 3in F0.Ifsis in the upper part of F, we seek another horizontal segment s0in the lower part of Fand we proceed as before, increasing the length of sand s0. (a) (b) Fig. 3. How to enlarge a segment of a convex face by any amount, (a) using parallel segments or (b) using three segments. Obviously, if sis not one of the si, the transformation in Fdoes not affect the segments of F0. But, if sis one of the sithen, on account of the first case, we consider a horizontal segment s0in the lower part of Fand a horizontal segment s00 in the upper part of F0. Increasing the length of s,s0and s00, and making a translation of all the segments of Fbetween sand s0, and all the segments of F0between sand s00, we obtain a new segment representation with the same convex faces as IG. Suppose now that IGhas nconvex faces, F1,...,F n, and let sbe a segment of a face F6=Fn, where Fnlies in the outer face of IG, i.e., the vertices v1,...,v k of G, corresponding to the segments s1,...,s kof Fn, lie on the outer face, and v2,...,v k−1are of degree two. Let us consider the graph G1=G−{v2,...,v k−1}. Removing the segments of IGcorresponding to v2,...,v k−1, we obtain a segment representation IG1of G1. Since IG1has n−1 faces, we can transform its segment representation into another representation which has the same convex faces, enlarging in any amount some of the segments. To obtain this new representation, we have to enlarge other segments in IG1besides s, but we have preserved the structure of the segments in the representation, so we are able to represent again the segments corresponding to v2,...,v k−1enlarging the length of one (or two) of them if necessary, obtaining a segment representation of G.ut Triangle-Free Planar Graphs as Segments Intersection Graphs 345 3 Triangle-Free Graphs Using the results of Barnette in [1], it can be deduced easily that every planar triangle-free graph which is a subdivision of a 3-connected graph can be reduced, by deleting edges and paths with internal vertices of degree two, to a subdivision of the complete graph K4in such a way that in each step we have a subdivision of a 3-connected graph. Moreover, if we fix a subgraph of Gwhich is a subdivision of K4,Gcan be reduced, by deleting edges and paths, to this subgraph. This result will allow us to build a segment representation in three directions of subdivisions of 3-connected graphs as follows. Firstly we build a segment representation of a subdivision of K4and then insert, in reverse order, the edges and paths that were removed to obtain from Gthe subdivision of K4. In order to do this, we need two basic operations: (1) insert a path between two segments of the same face and (2) join two segments of the same face. The second operation is, at least, as difficult as the first one, so we will concentrate only in the second operation. We can see, using Lemma 1, that by enlarging some segments, a segment representation with convex faces can be transformed into another one preserving the topology of the embedding. But this is not sufficient to carry on the second operation, so we need another kind of transformation. Fixing an index iand changing the drawing of the segments of the path Piof a face F, it is possible to draw a new convex face F0where the segments that were in Pibelong now to P0 i+1 or P0 i−1. The rest of the paths of F0only change in the length of some of the segments (see Figure 4). P1 P2 P3 P4 F P1' P2' P3' P4' F' ab c a b c Fig. 4. How to restructure a face through the path P1. In the segment representation, the change of the face Fto F0produces some changes in the faces adjacent to Falong the path Pi, and we obtain another segment representation with convex faces as in the proof of Lemma 1 (see Figure 5). When we change the drawing in the manner described above, we say that the face Fis restructured through the path Pi. We need at this point some new definitions. Given a 3-colored plane graph Gwith colors {h, o, v}, a path P={u1,...,u n}of Gis rare if it verifies one of the following conditions: 346 N. de Castro et al. Fig. 5. How to restructure the faces adjacents to the restructured face F. Case 1. u1is colored as h,u2as o, and unas v. Case 2. u1is colored as v,un−1as h, and unas o. Case 3. u1is colored as h,u2as o,un−1as h, and unas o. Case 4. u1is colored as o,u2as v,un−1as v, and unas h. A face of a graph is called rare if there exists a path Pi, with i=1,...,4, containing a rare subpath. We say that a rare face is repaired if we subdivide its rare path with a new vertex colored as vbetween u1and u2in the first and the third case, and between un−1and unin the second case, or a new vertex colored as hbetween u1and u2in the fourth case. On the other hand, notice that the vertical segments (except the last segment of P1and the last of P3) can be extended to the interior of a convex face F, the horizontal segments too if they are in P1or P3(except the first of P1and the first of P3), and the oblique segments if they are in P2or P4(except the first one of P1and P3, and the last one of P1and P3). Moreover, the horizontal segments in P2or P4can be extended to the interior of Fif there is a vertical segment to the right or an oblique segment to the left of them; and the oblique segments in P1or P3can be extended to the interior of Fif there is a horizontal segment to the right or a vertical to the left of them (see Figure 2). So, restructuring the paths and applying Lemma 1, we can transform the face Fin such a way that these transformations allow us to extend two segments inside Fto produce a new adjacency between them. In the following lemma, when we say that two segments sand tcan be joined by a path length k, it means a path s, s1,s 2,...,s k,t. Lemma 2. Let IGbe a segment representation of a plane graph Gand let s1 and s2be two distinct segments in a convex non-rare face F. Then IGcan be transformed into another segment representation I0 Gsatisfying 1. IGand I0 Ghave the same faces and face boundaries as G, and the faces of I0 Gare convex; 2. s1can be joined to s2by a segment path of length k, for all k>0,or directly if s1and s2have not the same direction inside the convex face F0, corresponding to F. Triangle-Free Planar Graphs as Segments Intersection Graphs 347 Proof. The proof falls naturally into two cases: the segments have the same direction, or they do not. In both cases, we have divided the proof in a sequence of subcases. Case 1: s1and s2have not the same direction. In this case, we can suppose that s1is vertical and s2is horizontal (similar arguments apply to the other configurations on the directions of the segments s1and s2). The subcases are the following: 1. s1and s2are in the same path Pi. a) s1and s2are in P2(respectively in P4). i. s1appears (clockwise) before s2. If an oblique segment precedes s2, by Lemma 1 the segments can be joined directly. Otherwise, the face must be restructured transforming P2into P0 3(respectively, P4into P0 1). ii. s2appears (clockwise) before s1. Since the face is not rare, s2pre- cedes a vertical segment. Then, by Lemma 1, the segments can be joined directly. b) s1and s2are in P1(respectively in P3). If s1appears (clockwise) before s2, by Lemma 1 the segments can be joined directly. If s2appears (clockwise) before s1, the face must be restructured transforming P1into P0 2 (respectively, P3into P0 4). 2. s1and s2are in different paths. If s2is in P2(respectively in P4) and it precedes an oblique segment and s1is in P3(respectively P1), the face must be restructured transforming P2into P0 1(respectively, P4into P0 3). Otherwise, by Lemma 1 the segments can be joined directly. Case 2: s1and s2have the same direction. In this case, it suffices to join the segments by a path of length 1, because this path can be substituted by any other of length greater than 1. Again there are several subcases: 1. Both are vertical segments. In this case, the segments can be joined by a path of length 1 directly using Lemma 1. 2. Both are horizontal segments. If the segments are in P2(respectively in P4) and the first one precedes an oblique segment, and a vertical segment precedes the second one, then the face must be restructured transforming P2 into P0 3(respectively, P4into P0 1). Otherwise, using Lemma 1 the segments can be joined directly. 3. Both are oblique segments. If the segments are in P1(respectively in P3), the first one precedes a vertical segment, and a horizontal segment precedes the second one, then the face must be restructured transforming P1into P0 2(respectively, P3into P0 4). Otherwise, they can be joined directly by Lemma 1. ut Now we prove: Lemma 3. Any triangle-free plane graph which is a subdivision of a 3-connected graph can be represented by segments in three directions. 348 N. de Castro et al. Proof. As Gis a triangle-free plane graph, in virtue of Gr¨otzsch’s Theorem [9], G admits a 3-coloring with the colors h,vand o(horizontal, vertical and oblique, respectively). Since Gis a subdivision of a 3-connected graph, we can find a vertex, not in the outer face of G, connected by three disjoint paths to three vertices in the outer face. These paths and the outer face determine a graph K, which is a subdivision of K4. Using Barnette’s results in [1] it is possible to build a sequence of graphs G1,...,G nand a sequence of paths Q1,...,Q nsuch that G1=G,Giis a subdivision of a 3-connected plane graph, Giis obtained from Gi−1by deleting the path Qi−1, and the graph obtained from Gndeleting Qnis K. When the path Qiis deleted, a new face Fappears in Gi+1 as the union of two faces in Gi. The boundary of Fcan be divided into two paths; on the one hand the path beginning in the first vertex of Qiand ending in the last one and, on the other hand, the rest of the boundary. If one of them is rare, we must repair Fsubdividing an edge with a new vertex (that we label as a repaired vertex), to make the face Fnon-rare. So, we can construct another sequence G0 1,...,G 0 n where G0 iis Giwith a new repaired vertex, if necessary. F F' F F' F F' F F' F F' F F' F F' F F' F F' F F' F' F F' F F' F F' F F' F F F' uu uu uu uu Fig. 6. How to remove the repaired vertex uin the four cases. It is easy to give a segment representation of K0with all its faces convex. It suffices to represent convexly the outer face of K0and proceed according to the Triangle-Free Planar Graphs as Segments Intersection Graphs 349 above remark. Using Lemma 2 it is possible to add the path Qito the segment representation of G0 i+1 to obtain a convex face representation of G0 i. In order to obtain a segment representation of the graph G, we must remove the repaired vertices. These vertices cannot be removed directly, so it is necessary to modify the representation. The four possible cases are illustrated in Figure 6. Notice that we could not remove the repaired vertices if the rare path would have exactly three segments u1,u2and u3, but this case it is not possible because joining u1with u3it will be form a triangle, and Gwas a triangle-free graph. ut We can now formulate our main result as follows: Theorem 1. Every triangle-free planar graph is the intersection graph of a set of segments in three directions. Proof. Let Gbe a triangle-free plane graph. Since Ghas no triangles, we can obtain a 3-coloring of Gusing Gr¨otszch’s Theorem [9]. The colors will be labeled as h,vand o(horizontal, vertical and oblique, respectively). We can build a new triangle-free plane graph G1, subdivision of a 3-connected graph, which contains Gas a subgraph, adding new vertices and edges joining the blocks of G, possibly subdividing some edges of the blocks of Gusing new vertices. If this is the case, these vertices are labeled as dummy vertices. When an added edge produces a triangle, we subdivide it, and when a new edge joins two vertices with the same color, we subdivide it too. We call these new vertices and edges virtual. All the new vertices (dummy and virtual) can be colored so that the 3-coloring is preserved . By Lemma 3, G1admits a segment representation. Out of this segment representation we must remove all the vertices and edges added. A virtual edge (or a path built with virtual edges and vertices) in the segment representation of G1is an adjacency between two segments (or a virtual path joining two segments). It suffices to break this adjacency and to shorten these segments (note that the segments do not cross, they only contact). The dummy vertices are removed as the repaired vertices in Lemma 3. ut 4 Concluding Remarks The hypothesis that the graph has no triangles can be relaxed in some cases. No doubt there exist planar graphs with triangles that admits segment representations (see Figure 1). The problem lies in the fact that we have followed a constructive proof to obtain a segment representation using the convex faces representation of a subdivision of a 3-connected graph. This construction would not be possible in general if the graph contains triangles, because if we fix the three directions of the segments we can observe that the graph in Figure 7 cannot be represented by non-crossing segments. In this example we see that a segment representation contains faces that do not correspond to faces of the embedding of the graph. So, the topology of the embedding of the plane graph cannot be preserved. This problem admits a