Informatica 30 (2006) 301-303 301 On the Crossing Number of Almost Planar Graphs Bojan Mohar Faculty of Mathematics and Physics Department of Mathematics University of Ljubljana Jadranska 19 1000 Ljubljana, Slovenia E-mail: bojan.mohar@uni-lj.si Keywords: planar graph, crossing number Received: May 8, 2005 If G is a plane graph and x,y e V(G), then the dual distance of x and y is equal to the minimum number of crossings of G with a closed curve in the plane joining x and y. Riskin [7] proved that if G0 is a 3-connected cubic planar graph, and x, y are its vertices at dual distance d, then the crossing number of the graph G0 + xy is equal to d. Riskin asked if his result holds for arbitrary 3-connected planar graphs. In this paper it is proved that this is not the case (not even for every 5-connected planar graph G0). Povzetek: Analizirana je Riskinova teza o planarnih grafih. 1 Introduction Crossing number minimization is one of the fundamental optimization problems in the sense that it is related to various other widely used notions. Besides its mathematical interest, there are numerous applications, most notably those in VLSI design [1,2, 3] and in combinatorial geometry [9]. We refer to [4, 8] and to [10] for more details about such applications. A drawing of a graph G is a representation of G in the Euclidean plane R2 where vertices are represented as distinct points and edges by simple polygonal arcs joining points that correspond to their endvertices. A drawing is clean if the interior of every arc representing an edge contains no points representing the vertices of G. If interiors of two arcs intersect or if an arc contains a vertex of G in its interior we speak about crossings of the drawing. More precisely, a crossing of D is a pair ({e, f },p), where e and f are distinct edges and p e R2 is a point that belongs to interiors of both arcs representing e and f in D. If the drawing is not clean, then the arc of an edge e may contain in its interior a point p e R2 that represents a vertex v of G. In such a case, the pair ({v, e}, p) is also referred to as a crossing of D. The number of crossings of D is denoted by cr (D) and is called the crossing number of the drawing D. The crossing number cr(G) of a graph G is the minimum cr(D) taken over all clean drawings D of G. A clean drawing D with cr(D) =0 is also called an embedding of G. By a plane graph we refer to a planar graph together with an embedding in the Euclidean plane. We shall identify a plane graph with its image in the plane. A nonplanar graph G is almost planar if it contains an edge e such that G - e is planar. Such an edge e is called a planarizing edge. It is easy to see that almost planar graphs can have arbitrarily large crossing number. In the sequel, we will consider almost planar graphs with a fixed planarizing edge e = xy, and will denote by G0 = G - e the corresponding planar subgraph. By a plane graph we mean a planar graph together with its embedding in the plane. Let G0 be a plane graph and let x,y be two of its vertices. A simple (polygonal) arc 7 : [0,1] ^ R2 is an (x, y)-arc if 7(0) = x and 7(1) = y. If j(t) is not a vertex of G0 for every t, 0 < t < 1, then we say that 7 is clean. For an (x, y)-arc 7 we define the crossing number of 7 with G0 as cr(7,Go) = \{t \ Y(t) e Go and 0 k. Figure 1: Part of the triangular lattice with side length 8 Proof. Let Hk be the planar graph that is obtained from the icosahedron by replacing all of its triangles, except one, with the dissection of the equilateral triangle with side of length k into equilateral triangles with sides of unit length (as shown in Figure 1 for k = 8). This graph is a near triangulation, all its faces are triangles, except one, whose length is 3k. We may assume that this is the outer face in a plane embedding of Hk. Its boundary is composed of three paths A, B, C of length k joining the original vertices a',b', cC of the icosahedron we started with. Now we add three new vertices, a, b, c and join a with all vertices on A, b with B, and c with C. This gives rise to a 5-connected near triangulation Gk whose outer face is the Figure 2: The graph Qk 6-gon aa'bb'cc'. Let us take 5 copies of the graph Gk and let ai,a'i,bi,b'i,ci, c'i be copies of the corresponding vertices on the outer face of the ith copy of Gk, i = 1,..., 5. Let Qk be the planar graph obtained from these copies by cyclically identifying bi with ai+i, adding edges bic'i+1 (i = 1,..., 5, indices modulo 5), and adding two vertices x and y such that x is joined to a1,... ,a5 and y is joined to c1,..., c5. See Figure 2. The obtained graph Qk is planar and it is not difficult to verify that it is 5-connected. It is easy to see that d*(x,y) = k + 2 in Qk. By putting the vertex x close to y, so that we can draw the edge xy without introducing crossings with other edges, and then redrawing the edges from x to its neighbors as shown in Figure 2, a drawing of Qk + xy is obtained whose crossing number is 11. i—i Figure 3: A planar graph for which two flips are needed The construction of Theorem 2.1 can be generalized such that a similar redrawing as made above for x is necessary also for y (in order to bring these two vertices close together). Such an example is shown in Figure 3, where x CROSSING NUMBER OF ALMOST PLANAR GRAPHS Informatica 30 (2006) 301-303 303 and y are vertices in the centers of the small circular grids on the picture, and where the bold lines represent a "thick" barrier similar to the one used in the graph Qk in Figure 2. In Figure 4, an optimum drawing of G0 + xy is shown, where the edge xy is represented by the broken line. In this drawing, neighborhoods of x and y, are redrawn inside the faces denoted by A and B (respectively) in Figure 3. At the first sight the redrawing described in the above example seems like the worst possibility which may happen - to "flip" a part of the graph containing x and to "flip" a part containing y. If this would be the only possibility of making the crossing number smaller than the one coming from the planar drawing of G0, this would most likely give rise to a polynomial time algorithm for computing the crossing number of graphs that are just one edge away from a 3-connected planar graph. Figure 4: An optimum drawing of G0 + xy Unfortunately, some more complicated examples show that there are other ways for shortcutting the dual distance from x to y. (Such an example was produced in a discussion with Thomas Bohme and Neil Robertson whose help is greatly acknowledged.) Despite such examples, the following question may still have a positive answer: Problem 2.2. Is there a polynomial time algorithm which would determine the crossing number of G0 + xy if G0 is planar. Acknowledgement Supported in part by the Ministry of Higher Education, Science and Technology of Slovenia, Research Program P1-0507-0101 and Research Project L1-5014-0101. References [1] S.N. Bhatt, F.T. Leighton, A framework for solving VLSI graph layout problems, J. Comput. System Sci. 28 (1984) 300-343. [2] F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, Mass., 1983. [3] F. T. Leighton, New lower bound techniques for VLSI, Math. Systems Theory 17 (1984) 47-70. [4] A. Liebers, Planarizing graphs—a survey and annotated bibliography, J. Graph Algorithms Appl. 5 (2001) 74 pp. [5] B. Mohar, Crossing number of almost planar graphs, preprint, 2005. [6] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, 2001. [7] A. Riskin, The crossing number of a cubic plane polyhedral map plus an edge, Studia Sci. Math. Hungar. 31 (1996) 405-413. [8] F. Shahrokhi, O. Sykora, L.A. Sz6kely, I. Vrt'o, Crossing numbers: bounds and applications. Intuitive geometry (Budapest, 1995), 179-206, J. Bolyai Math. Soc., Budapest, 1997. [9] L.A. Sz6kely, A successful concept for measuring non-planarity of graphs: the crossing number, Discrete Math. 276 (2004) 331-352. [10] I. Vrt'o, Crossing number of graphs: A bibliography. ftp://ftp.ifi.savba.sk/ pub/imrich/crobib.pdf