On Line Graphs With Crossing Number 3

On Line Graphs with Crossing Number 3

Mallikarjun Ghaleppa, Amit Kumar Yadav, Amabelle Oliva Enanoria

Mathematics and Computing Unit, Preparatory Studies Center, University of Technology and Applied Sciences, Ibra, Oman.

DOI: https://dx.doi.org/10.47772/IJRISS.2025.9010168

Received: 03 January 2025; Accepted: 07 January 2025; Published: 10 February 2025

ABSTRACT

Kulli, Akka and Beineke obtained a characterization of planar graphs whose line graphs have crossing number 1. Akka, Jendrol, Kles^vc^v and Panshetty presented a characteri- zation of planar graphs whose line graphs have crossing number 2. The main result of this paper is a characterization of graphs whose line graphs have crossing number 3.

The primary contribution of this paper is the characterization of graphs whose line graphs have a crossing number of three. Let be a graph and its line graph. The main result identifies necessary and sufficient structural properties of that ensure has a crossing number of three.

Further research can expand on this work by examining families of graphs that exhibit higher crossing numbers and exploring computational approaches for practical applications in visualization and optimization.

Keywords and phrases. Line graph, Crossing number, Characterization, Planar graphs. 2010 Mathematics Subject Classification: Primary 05C78; Secondary 05C76.

INTRODUCTION

A graph G is said to be planar when it is isomorphic to a graph G(π) whose vertex set V is a vertex set in a plane π while the edges are Jordan curves (non – self intersecting) in π such that two different edges have at-most end vertices in common. A diagram of a planar graph G which conforms with these conditions is called a planar representation of G. Two planar representations of G will be regarded as distinct if they cannot be made to coincide with another by elastic deformation of the plane.

All graphs considered here are finite, undirected and without loops or multiple edges. For other definitions see [7].

With every graph G there is associated a graph L(G) called the line graph of G in such a way that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. This concept originated by Whitney [12]. The crossing number C_r(G) of a graph G is the least number of intersections of pairs of edges in any embedding of G in the Plane. Obviously, G is planar if and only if C_r(G) = 0. This concept is contained in the Turan’s bricks factory problem.

J.Sedlac^vek [11] has obtained that the line graph of graph G is planar if and only if G is planar, the degree of each vertex is at most 4 and all vertices of degree 4 are cut vertices. By using this result D.L. Greenwell and R.L. Hemminger [5] established that a graph has a planar line graph if and only if it has no subgraph homeomorphic to K_3,3, K_1,5, P₄ + K₁ or K₂ + K₃. Kulli, Akka and Beineke [10] obtained a characterization of planar graphs whose line graphs have crossing number 1. In [1], the same characterization was established in terms of forbidden subgraphs. Jendrol^v and  Kles^vc^v [9] presented a characterization of a nonplanar graphs to have a line graph with crossing number 1. This corrects some errors in Kulli et.al [10]. Akka, Jendrol^v, Kles^vc^v and Panshetty [2] established a characterization of planar graphs whose line graphs have crossing number 2. Akka and Mallikarjun Ghaleppa [3] obtained a characterization of a nonplanar graphs to have a line graph with crossing number 2. This corrects some errors in Akka et.al [2]. Primary purpose of this paper is to establish a characterization of a nonplanar graph to have a line graph with crossing number 3.

If e = uv an edge of G, the corresponding vertex of L(G) is denoted by l(e) or l(uv). Every vertex x of G with degree p where p ∈ {2, 3, …, ∆(G)} induces in L(G) the clique on p vertices which we denote by K^x. The following Theorems and Lemmas will be useful in proof of our main Theorem.

Theorem A [11]. The line graph of a planar graph G is planar if and only if ∆(G) ≤ 4 and every vertex of degree 4 is a cut-vertex.

We may revise Theorem A to read:

Theorem B. The line graph of a planar graph G has crossing number 0 if and only if ∆(G) ≤ 4 and every vertex of degree 4 is a cut vertex.

Theorem C [10]. The line graph of any nonplanar graph has crossing number at-least 3.

Theorem D [10]. The line graph of a planar graph G has a crossing number 1 if and only if

(1) or (2) holds:

1. ∆(G) = 4 and there is a unique noncut-vertex of degree
2. ∆(G) = 5, every vertex of degree 4 is a cut-vertex, there is a unique vertex of degree 5 and it is a cut-vertex having at-most 3 incident edges in any block.

Theorem E [2]. The line graph L(G) of a planar graph G has crossing number 2 if and only one of the following conditions holds:

1. ∆(G) = 4 and exactly two of the vertices of degree 4 are not cut vertices of
2. ∆(G) = 5, there are exactly two vertices of degree 5, each is a cut-vertex of G and each has at most 3 incident edges in any block. Every vertex of degree 4 is a cut-vertex.
3. ∆(G) = 5, there is a unique vertex of degree 5, it is a cut-vertex having at-most 3 incident edges in any block, and there is a unique not cut-vertex of degree 4 in G.
4. ∆(G) = 5, there is a unique vertex of degree 5, it is a cut-vertex having exactly 4 incident edges in one block, and, moreover, either at-least one of the 4 vertices adjacent to the vertex of degree 5 in the block has degree 2 or in the block there is a vertex of degree 2, which together with the vertex of degree 5 forms a cut-set of the Every vertex of degree 4 is a cut-vertex of G.

Theorem F [9]. Let G be a nonplanar graph. Then C_r(L(G)) = 1 if and only if the following conditions hold:

1. C_r(G) = 1
2. ∆(G) ≤ 4, and every vertex of degree 4 is a cut-vertex of
3. There exists a drawing of G in the plane with exactly one crossing in which each crossed edge is incident with a vertex of degree 2.

Lemma 1 [2]. If in G there is a vertex of degree 5 which is not a cut-vertex of G then L(G) has at-least 3 crossings.

Lemma 2 [2]. Let v be a cut-vertex of degree 5 in G and let 4 edges incident with v be in one block B of G. If in B all vertices adjacent to v have degree at-least 3 and there is no vertex u of degree 2 such that the vertex set {u, v} forms a cut-set of B, then L(G) has at-least 3 crossings.

Lemma 3 [2]. Let G¹ be a graph obtained from G by the transformation shown in fig 1 were v is a vertex of degree 4 which is not a cut-vertex of G. If 1 ≤ C_r(L(G)) < 3 then C_r(L(G¹)) < C_r(L(G))

Lemma 4 [9]. C_r(G) < C_r(L(G)).

MAIN RESULT

Theorem. The line graph of a graph (planar or nonplanar) G has crossing number 3 if and only if one of the following conditions holds:

1. ∆(G) = 3, and G has a unique induced subgraph K_3,3
2. ∆(G) = 4, and G has exactly 3 non-cut-vertices of degree
3. ∆(G) = 5, and every vertex of degree 4 is a cut-vertex, there are exactly 3 vertices of degree 5 and each has at-most 3 edges in any block
4. ∆(G) = 5, there is a unique noncut-vertex of degree 4, and there are exactly two vertices of degree 5 and each has at-most 3 edges in any block
5. ∆(G) = 5, there are exactly 2 non-cut-vertices of degree 4 and there is a unique vertex of degree 5 and it has at-most 3 edges in any block
6. ∆(G) = 5, there is a unique noncut-vertex of degree 4, and there is a unique vertex v of degree 5 and it has exactly 4 edges in any block and moreover, either at-least one of the 4 vertices adjacent v in the block has degree 2 or in the block there is a vertex of degree 2 which together with v forms a cut-set of the block.
7. ∆(G) = 5, there is a unique vertex of degree 5 and it has at-most 3 edges in any block and there is a unique vertex v of degree 5 and it has exactly 4 edges in any block and more over either at-least one of the 4 vertices adjacent to v in the block has degree 2 or in the block there is a vertex of degree 2 which together with v forms a cut-set of the Every vertex of degree 4 is a cut-vertex of G
8. ∆(G) = 5, there is a unique vertex v of degree 5 and it has exactly 4 vertices in any block B and in B all vertices adjacent to v have degree at-least 3 and there is no vertex u of degree 2 such that the vertex set {u, v} forms a cut-set of B.
9. ∆(G) = 5, every vertex of degree 4 is a cut-vertex, and there is a unique non-cut-vertex of degree 5.
10. ∆(G) = 6, there is a unique cut-vertex of degree 6 and it has at-most 3 incident edges in any

Proof . Assume that the line graph L(G) of a graph G has crossing number 3. Then by Theorem E and Theorem F, we have a graph G is either planar or nonplanar.

Case I. Let G be a nonplanar graph. By Kuratowski’s Theorem on planar graph, it is sufficient to prove that L(K_3,3) have crossing number at-least 3. The graph L(K_3,3) is isomorphic to C₃XC₃ and Harary et.al [8] have show that the crossing of this graph is 3. Thus the line graph of K_3,3 has at-least 3 crossings in every drawing as was to be shown. Hence K_3,3 is a subgraph of G.

Case II. Let G be a planar graph. Assume that the line graph L(G) of a planar graph G has crossing number 3. Then by Theorem B, we have ∆(G) ≤ 4.

First we suppose that ∆(G) = 4. It follows from Theorem B and Theorem E that G has at-least 3 non-cut-vertices of degree 4. Assume that G has at-least 4 non-cut-vertices of degree 4. Applying Lemma 3 to one of these vertices we can obtain G¹ with 3 non-cut-vertices of degree 4 whose line graph has fewer than three crossings. This contradicts Theorem E. Hence G has exactly 3 non-cut-vertices of degree 4.

Suppose ∆(G) = 5. By Lemma 1, every vertex of degree 5 is a cut-vertex. G has at-most 3 vertices of degree 5, otherwise L(G) has at-least 4 subgraphs isomorphic to K₅ each with at-least one crossing among its edges. Suppose G has 3 cut-vertices u,v and w of degree 5 and let u has 4 incident edges in one block. Theorem D implies that u,v and w are in the same block of Without loss of generality we may suppose that they are not mutually adjacent, because by inserting a vertex of degree 2 between u,v; v,w or w,u we obtained a graph whose line graph has no more crosings than L(G). In every good drawing of L(G) there is at-least one crossings among the edges of K^v_s. Hence by contracting the edges of K^v_s into one vertex we obtained a line graph of a graph containing u and w each with 4 incident edges in one block. This line graph has crossing number at-most two which contradicts the Theorem D. Thus each of u,v and w has at-most 3 incident edges in a block. More-over using Lemma 3 and Theorem D, one can easy to see that very vertex of degree 4 is a cut-vertex.

Assume now there are exactly two vertices v₁ and v₂ of degree 5 which are cut-vertices of G. If each v_i has at-most 3 incident edges in one block, then by Theorem D there are in G, at-least two non-cut-vertices of degree 4. By Lemma 3 and Theorem D, it is easy to see that in this case there is a unique vertex of degree 4 that is not a cut-vertex of G.

Suppose now there is a unique vertex v of degree 5 which is a cut-vertex of G. If v has at-most 3 incident edges in one block then by Lemma 3 and Theorem D, there are in G at-least 2 non-cut-vertices of degree 4. By Lemma 3 and Theorem D, one can easily prove that in this case there are exactly two non-cut-vertices of degree 4 in G.

Let v be a unique cut-vertex of degree 5 in G and it has exactly 4 incident edges in one block. By Lemma 3 and Theorem D it is easy to see that in this case there is a unique non-cut-vertices of degree 4 in G. Moreover, at-least one vertex adjacent to v in the block with 4 edges incident with v has degree 2 or in that block there is a vertex of degree 2 which together with v from a cut-set of the block. Otherwise by Lemma 2, L(G) contains at-least 4 crossings.

G has at-most one vertex of degree 5 it has at-most 3 edges in any block otherwise L(G) contains at-least two subgraphs isomorphic to K₅, each with at-least one crossing among its edges. Suppose G has two cut-vertices u and v of degree 5 and let u has 4 incident edges in one block. Theorem D implies that both u and v are in the same block of G. Without loss of generality, we may suppose that they are not adjacent because by inserting a vertex of degree 2 between u and v. We obtained a graph whose line graph has no more crossings than L(G). In every good drawing of L(G) there is at-least one crossing among the edges of K^v_s. Thus by contracting the edges of K^v_s in to one vertex we obtained a line graph of a graph containing u with 4 incident edges in one block. This line graph has crossing number at-most two (See Theorem E). These crossings together with one crossing of K^v_s L(G) has 3 crossings.

Let v be a unique cut-vertex of degree 5 in G and it has exactly 4 incident edges in a block by Lemma 3 and Theorem D every vertex of degree 4 is a cut-vertex of G. More-over at-least one vertex adjacent to v in the block with 4 edges incident with v has degree 2 or in that block there is a vertex of degree 2 which together with v form a cut-set of the block, then L(G) has two crossings, a contradiction. Thus every vertex adjacent to v in B has degree 3.

Suppose G has at-least one non-cut-vertex v of degree 5. Then G has a subgraph P₅ + v, the edges incident with a non-cut-vertex v of degree 5 in G form in L(G) the complete graph on 5 vertices. We note in every good drawing of L(G) at-least one crossing exist in K₅, since contradicting the edges of L(G) not incident with the vertices of K₅ results in a graph isomorphic to K₆ and C_r(K₆) = 3 by Theorem E, there is in G at-least one non-cut-vertex of degree 4. By Lemma 3 and Theorem D, it is easy to see that in this case there is unique vertex of degree 4 that is not a cut-vertex of G. L(G) has at-least 4 crossings, a contradiction. Thus G has a unique non-cut-vertex of degree 5 and every vertex of degree 4 is a cut-vertex.

Suppose \( \Delta(G) \geq 7 \) and let \( \deg v = n \geq 7 \). Then, \( L(G) \) contains a subgraph \( K_7 \) with at least 4 crossings in its edges [6]. It is known that the crossing number of \( K_{n+1} \), for \( n \geq 6 \), is given by \( Cr(K_7) = Cr(K_{6+1}) = \frac{1}{4} \left( \frac{6+1}{2} \right) \left( \frac{6}{2} \right) \left( \frac{(6-2)/2}{2} \right) > 3 \), which leads to a contradiction. It remains to prove that \( v \) is a unique cut-vertex of degree 6 in \( G \) and has exactly 4 incident edges in one block. By Lemma 3 and Theorem D, every vertex of degree 4 is a cut-vertex of \( G \), and since \( L(G) \) has at least 4 crossings, we reach another contradiction.

Conversely first we suppose that the conditions (1) to (10) hold. Assume (1) holds then by Theorem E, L(G) has crossing number at-least 3. By Lemma 4, C_r(G) = 1 and G has a unique induced subgraph K_3,3.

If (2) holds then v₁, v₂, v₃ (mutually adjacent or nonadjacent) are 3 non-cut-vertices of degree Using transformation from figure 1(a) On three vertices v_i from G¹ from G by making the transformation in Fig 1(b). Then L(G¹) is planar and must contain the configuration in Fig 2(a). This can be transformed to give rise to a drawing of L(G) with only 3 crossings (See Fig 2(b)).

Now assume that the condition (3) holds. Let v₁, v₂ and v₃ (mutually adjacent or nonadjacent) be three vertices of degree 5. Then the edges incident with v₁ can be split into two sets of sizes 2 and 3 such way that no edges in different sets are in the same block. Form G¹¹ from G by the transformation as in Fig 3(a). Then by Theorem D, C_r(G¹¹) = 1, f is a cut-vertex of L(G¹¹) and the vertices of the block of L(G¹¹) containing the vertices c,d,e and f but other than these vertices lie in the region with c,d and e on its boundary. We can assume that the vertices of the block of L(G¹¹) containing the edge {a, b} other than a,b and f lie in the triangular region with the vertices a, b and f on its boundary. The transformation of L(G¹¹) into L(G) with exactly 3 crossings as shown in Fig 3(b).

Figure 1:

Figure 2:

Figure 3:

Next suppose that the condition (4) holds. The edges incident with vertices v_i i=1,2 of degree 5 can be split into sets of sizes 2 and 3 so that no edges in different sets are in the same block. Transform G to G¹¹ as in Fig 3(a). Then ∆(G¹¹) = 4 and G¹¹ contains one non-cut-vertex u of degree 4. By Theorem D, C_r(L(G¹¹)) = 1 and the line graph of the block containing u is in L(G¹¹) (See Fig 3(a)), either in the triangular region with a,b and f on its boundary or in the region with c,d and e on its boundary. This can be again transformed to obtained a drawing of L(G) with two additional crossings as shown in Fig 3(b).

Suppose that the condition (5) holds. The edges at the vertex v of degree 5 can be split into two sets of size 2 and 3 so that no edges in different sets are in the same block. Transform G to G¹¹ as in Fig 3(a). Then L(G¹¹) is again planar (See Fig 3(b)) and L(G) can be drawn with one crossing as indicated in Fig 3(b). Also G has three non-cut-vertices v₁, v₂ and v₃ of degree 4 each. It is easy to seen from Theorem A that they must lie in the same block of G. By inserting a vertex of degree two in between each pair if necessary, we may assume they are not adjacent. In a drawing of L(G) with one crossing, the vertices from the 4 edges at v₁, v₂ or v₃ must form a complete 4- graph of either type 1 or type 2 in Fig 4 and not both can be of type 1. Suppose three are of type 2 (See Fig 5(a)). Then in G edges e₁, e₂ and e₃

Figure 4:

are on cycle that contains only one other edge at each of v₁, v₂ and v₃. In L(G) such a cycle must give 3 crossings. Similarly if v_i gives rise of type 1 and v_j of type 2. It follows that L(G) has at-least 3 additional crossings (Fig 5(b)).

Now assume (6) holds. Let u and v be the vertices of degree 2 and 5 respectively. Let a,b,c,d and e be edges incident with the vertex v such that e is a bridge and the other edges belong to a subgraph of G₂ where G₂ is connected subgraph of G not containing e. Let G₁ be a subgraph of G induced by edges of G not belonging to G₂. By Theorem D, C_r(L(G₂)) = 1 and L(G₁) is planar. Because L(G₂ − u) is planar (See Theorem B), the graph L(G₂) can be drawn in such a way that the edges of the subgraph K₄ of L(G₂₎ induced by the edges a,b c and d do not cross one another and one crossing of L(G₂) is realized with one of these edges and the edge (in fact K₂) which associated in L(G) to the vertex u. Let us draw L(G₁) (of course without crossings) in to a triangular region of K₄ not containing inside any vertex of L(G₂), in such a way that the

Figure 5:

vertex e is on outer face with respect to the drawing of L(G₁). Then we can join the vertex e with the vertices a,b.c and d of L(G₂) not producing more than one crossing.

All that remains is to show that any vertex u of degree 4 must be not-cut-vertex. Suppose there are at-least two non-cut-vertices w and z of degree 4. Then by Theorem A, there are two crossings. The result in a drawing of L(G) having at-least 4 crossings, a contradiction. Thus G has exactly one non-cut-vertex of degree 4. Therefore L(G) has exactly 3 crossings.

Assume (7) holds. It is easily see that G cannot have 3 vertices of degree 5, So let v₁ and v₂ (adjacent or not-adjacent) be the vertices each has degree 5. We observe that if v₁ has 4 (it may have all 5) of its edges a,b ,c and d in one block then the line graph of that block has crossing number at-least 1. So if L(G) has only one crossing, the fifth line e in G at v₁ must have appear in an optimal drawing of L(G) as in Fig (6).But a and b lies in a block, so there must be a cycle containing them and neither c or d.

It follows that L(G) would have crossing number at-least 2 so v₁ has at most 3 edges in any block. So L(G) must have crossing number at-least 2. So v₁ has at-most 3 edges in a block and v₂ has 4 edges in a block.

Figure 6:

It remains to prove that v₂ is a cut-vertex of degree 5 having exactly 4 incident edges a,b,c and d in one block. By case 6, the line graph L(G) has two more crossings. So L(G) must have crossing number 3.

Assume (8) holds. Then Lemma 2, L(G) has 3 crossings.

Assume (9) holds. Suppose degv = 5 and v is not a cut-vertex of G. By Lemma 1, L(G) has at-most 3 crossings. It sufficient to prove that C_r(L(G)) ≥ 3. Let a,b,c,d and e be the edges incident to v and let f,g,h and i be the edges not incident with v. Removal of an edges for i which is incident to a vertex of degree 2 in the block we get there is a unique vertex of degree 5, it is a cut-vertex having exactly 4 incident edges in one block. Then by Theorem E, L(G) has at-least 2 crossings. Adding an edge f (or i) in an optimal drawing increases one crossing. Thus C_r(L(G)) ≥ 3.

Assume (10) holds. Let v be the vertex of degree 6. We observed that if v has at-least 4 of its lines a,b,c and d in one block then the line graph of that block has crossing number at-least one. So if L(G) has only one crossing the fifth and sixth edges e and f in G at v must appear in an optimal drawing of L(G) as in Fig 7.

Figure 7:

But a and b lie in a block, so there must be a cycle containing them and neither c or d. It follows that L(G) would have crossing number at-least 3. So v has at-most 3 edges in any one block. This complete the proof.

REFERENCES

1. D.G. Akka and S.V. Panshetty, Forbidden subgraphs for graphs with line graphs of crossing number ≤ 1. Periodical Mathematica, Hungarica, Vol. 26 (1993) 175-185.
2. D.G. Akka, S. Jendrol, M. Klesvcv and S.V. Panshetty, On line graphs with crossing number 2, Univ. Beadrad Publ, Elektrotehn, Fak, Ser. Mat. Vol. 8 (1997) 3-8.
3. D.G. Akka and Mallikarjun Ghaleppa, on line graphs whose line graphs have crossing number 2 (pre-print).
4. D. Archdeacon and R.B. Richtor, On the Parity of crossing number, J. Graph Theory, Vol. 12 (1988) 307-310.
5. D.L. Greenwell and R.L. Hemminger, Forbidden subgraphs for graphs with planar line graphs, Discrete Math., Vol. 2, No. 1 (1972) 31-34.
6. R.K. Guy, Latest results on crossing numbers, In Recent Trends in Graph Theory, Springer N. Y (1997) 143- 154.
7. F. Harary, Graph Theory, Addison-Wesley Reading Mas (1969).
8. F. Harary, P.C. Kain and A.J. Schwenk, Toroidal graphs with arbitrary high crossing numbers, Nanta Math. Vol. 6 (1973) 58-67.
9. S. Jendrol and Marian Klesvcv, on graphs whose line graphs have crossing number 1, J. Graph Theory, Vol.37 (2001) 181-188.
10. V.R. Kulli, D.G. Akka and L.W. Beineke, On line graphs with crossing number 1, J. Graph Theory, Vol. 3 (1979) 87-90.
11. J. Sedlacvek, some properties of interchange graphs in: M, Fieler, ed. Theory of graphs and its application (Progue 1962, reprinted by Academic Press, N.Y. (1962)) 145-150.
12. H. Whitney, Congruent graphs and connectivity of graphs, Amer. J. Math. Vol. 54 (1932) 150-168.