# On the crossing number of almost planar graphs.

If G is a plane graph and x, y [member of] 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 [G.sub.0] is a 3-connected cubic planar graph, and x, y are its
vertices at dual distance d, then the crossing number of the graph
[G.sub.0]) + 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
[G.sub.0]).

Povzetek: Analizirana je Riskinova teza o planarnih grafih.

Keywords: planar graph, crossing number

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 [[??].sup.2] 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 [member of] [[??].sup.2] 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 [member of] [[??].sup.2] 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(D0) 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 identity 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 [G.sub.0] - G - e the corresponding planar subgraph. By a plane graph we mean a planar graph together with its embedding in the plane.

Let [G.sub.0] be a plane graph and let x, y be two of its vertices. A simple (polygonal) arc [gamma] : [0, 1] [right arrow] [[??].sup.2] is an (x, y)-arc if [gamma](0) = x and [gamma](1) = y. If [gamma] (t) is not a vertex of [G.sub.0] for every t, 0 < t < 1, then we say that [gamma] is clean. For an (x, y)-arc [gamma] we define the crossing number of [gamma] with [G.sub.0] as

cr([gamma],[G.sub.0]) = |{t | [gamma](t) [member of] [G.sub.0] and 0 < t < 1}|.

Using this notation, we define the dual distance

[d.sup.*](x, y) = min{cr([gamma], [G.sub.0]) | [gamma] is a clean (x, y)-arc}

and the facial distance between x and y,

d'(x, y) = min{cr([gamma] [G.sub.0]) | [gamma] is an (x, y)-arc}.

Clearly, d'(x, y) [less than or equal to] [d.sup.*](x, y).

Let [G.sup.*.sub.x,y] be the geometric dual graph of the plane graph [G.sub.0] - x - y. Then [d.sup.*] (x, y) is equal to the distance in [G.sup.*.sub.x,y] between the two vertices corresponding to the faces of [G.sub.0] x - y containing x and y. This shows that [d.sup.*](x,y) can be computed in linear time. Similarly, one can compute d'(x, y) in linear time by using the vertex-face incidence graph (see [6]).

Proposition 1.1. If [G.sub.0] is a planar graph and x, y [member of] V([G.sub.0]), then for every embedding of [G.sub.0] in the plane, we have cr([G.sub.0] + xy) [less than or equal to] [d.sup.*](x, y).

Proposition 1.1 is clear from the definition of [d.sup.*]. It shows that it is of interest to determine the minimum [d.sup.*] (x, y) taken over all embeddings of [G.sub.0] in the plane. We refer to [5] for more details and some further extensions.

Riskin [7] proved the following strengthening of Proposition 1.1 in a special case when [G.sub.0] is 3-connected and cubic:

Theorem 1.2. If [G.sub.0] is a 3-connected cubic planar graph, Then

cr([G.sub.0] + xy) = d'(x, y).

Let us observe that d'(x, y) = [d.sup.*] (x, y) if [G.sub.0] is a cubic graph.

Riskin asked in [7] if Theorem 1.2 holds for arbitrary 3-connected planar graphs. In this paper we show that this is not the case (not even for every 5-connected planar graph [G.sub.0]).

2 Strange examples

In this section we provide a negative answer to the aforementioned question of Riskin [7] who asked if it is true that for every 3-connected plane graph [G.sub.0] and any two of its vertices x, y, the crossing number of [G.sub.0] + xy equals [d.sup.*] (x, y).

Theorem 2.1. For every integer k, there exists a 5-connected planar graph [G.sub.0] and two vertices x, y [member of] V([G.sub.0]) such that cr([G.sub.0] + xy) [less than or equal to] 11 and [d.sup.*] (x, y) [greater than or equal to] k.

Proof. Let [H.sub.k] 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 [H.sub.k]. Its boundary is composed of three paths A, B, C of length k joining the original vertices a', b', c' 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 [G.sub.k] whose outer face is the 6-gon aa'bb'cc'. Let us take 5 copies of the graph [G.sub.k] and let [a.sub.i], [a'.sub.i], [b.sub.i], [b'.sub.i], [c.sub.i], [c'.sub.i] be copies of the corresponding vertices on the outer face of the ith copy of [G.sub.k], i = 1,..., 5. Let [Q.sub.k] be the planar graph obtained from these copies by cyclically identifying [b.sub.i] with [a.sub.i+1], adding edges [b'.sub.i][c'.sub.i+1] (i = 1,..., 5, indices modulo 5), and adding two vertices x and y such that x is joined to [a.sub.1],..., [a.sub.5] and y is joined to [c.sub.1],..., [c.sub.5]. See Figure 2. The obtained graph [Q.sub.k] is planar and it is not difficult to verify that it is 5-connected.

[FIGURES 1-2 OMITTED]

It is easy to see that [d.sup.*] (x, y) = k + 2 in [Q.sub.k]. 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 [Q.sub.k] + xy is obtained whose crossing number is 11.

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 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 [Q.sub.k] in Figure 2. In Figure 4, an optimum drawing of [G.sub.0] + 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.

[FIGURES 3-4 OMITTED]

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 [G.sub.0], 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.

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 [G.sub.0] + xy if [G.sub.0] 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. Szekely, I. Vrt'o, Crossing numbers: bounds and applications. Intuitive geometry (Budapest, 1995), 179-206, J. Bolyai Math. Soc., Budapest, 1997.

[9] L.A. Szekely, 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

Bojan Mohar

Faculty of Mathematics and Physics

Department of Mathematics

University of Ljubijana

Jadranska 19

1000 Ljubljana, Slovenia

E-mail: bojan.mohar@uni-lj.si

Received: May 8, 2005

Povzetek: Analizirana je Riskinova teza o planarnih grafih.

Keywords: planar graph, crossing number

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 [[??].sup.2] 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 [member of] [[??].sup.2] 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 [member of] [[??].sup.2] 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(D0) 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 identity 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 [G.sub.0] - G - e the corresponding planar subgraph. By a plane graph we mean a planar graph together with its embedding in the plane.

Let [G.sub.0] be a plane graph and let x, y be two of its vertices. A simple (polygonal) arc [gamma] : [0, 1] [right arrow] [[??].sup.2] is an (x, y)-arc if [gamma](0) = x and [gamma](1) = y. If [gamma] (t) is not a vertex of [G.sub.0] for every t, 0 < t < 1, then we say that [gamma] is clean. For an (x, y)-arc [gamma] we define the crossing number of [gamma] with [G.sub.0] as

cr([gamma],[G.sub.0]) = |{t | [gamma](t) [member of] [G.sub.0] and 0 < t < 1}|.

Using this notation, we define the dual distance

[d.sup.*](x, y) = min{cr([gamma], [G.sub.0]) | [gamma] is a clean (x, y)-arc}

and the facial distance between x and y,

d'(x, y) = min{cr([gamma] [G.sub.0]) | [gamma] is an (x, y)-arc}.

Clearly, d'(x, y) [less than or equal to] [d.sup.*](x, y).

Let [G.sup.*.sub.x,y] be the geometric dual graph of the plane graph [G.sub.0] - x - y. Then [d.sup.*] (x, y) is equal to the distance in [G.sup.*.sub.x,y] between the two vertices corresponding to the faces of [G.sub.0] x - y containing x and y. This shows that [d.sup.*](x,y) can be computed in linear time. Similarly, one can compute d'(x, y) in linear time by using the vertex-face incidence graph (see [6]).

Proposition 1.1. If [G.sub.0] is a planar graph and x, y [member of] V([G.sub.0]), then for every embedding of [G.sub.0] in the plane, we have cr([G.sub.0] + xy) [less than or equal to] [d.sup.*](x, y).

Proposition 1.1 is clear from the definition of [d.sup.*]. It shows that it is of interest to determine the minimum [d.sup.*] (x, y) taken over all embeddings of [G.sub.0] in the plane. We refer to [5] for more details and some further extensions.

Riskin [7] proved the following strengthening of Proposition 1.1 in a special case when [G.sub.0] is 3-connected and cubic:

Theorem 1.2. If [G.sub.0] is a 3-connected cubic planar graph, Then

cr([G.sub.0] + xy) = d'(x, y).

Let us observe that d'(x, y) = [d.sup.*] (x, y) if [G.sub.0] is a cubic graph.

Riskin asked in [7] if Theorem 1.2 holds for arbitrary 3-connected planar graphs. In this paper we show that this is not the case (not even for every 5-connected planar graph [G.sub.0]).

2 Strange examples

In this section we provide a negative answer to the aforementioned question of Riskin [7] who asked if it is true that for every 3-connected plane graph [G.sub.0] and any two of its vertices x, y, the crossing number of [G.sub.0] + xy equals [d.sup.*] (x, y).

Theorem 2.1. For every integer k, there exists a 5-connected planar graph [G.sub.0] and two vertices x, y [member of] V([G.sub.0]) such that cr([G.sub.0] + xy) [less than or equal to] 11 and [d.sup.*] (x, y) [greater than or equal to] k.

Proof. Let [H.sub.k] 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 [H.sub.k]. Its boundary is composed of three paths A, B, C of length k joining the original vertices a', b', c' 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 [G.sub.k] whose outer face is the 6-gon aa'bb'cc'. Let us take 5 copies of the graph [G.sub.k] and let [a.sub.i], [a'.sub.i], [b.sub.i], [b'.sub.i], [c.sub.i], [c'.sub.i] be copies of the corresponding vertices on the outer face of the ith copy of [G.sub.k], i = 1,..., 5. Let [Q.sub.k] be the planar graph obtained from these copies by cyclically identifying [b.sub.i] with [a.sub.i+1], adding edges [b'.sub.i][c'.sub.i+1] (i = 1,..., 5, indices modulo 5), and adding two vertices x and y such that x is joined to [a.sub.1],..., [a.sub.5] and y is joined to [c.sub.1],..., [c.sub.5]. See Figure 2. The obtained graph [Q.sub.k] is planar and it is not difficult to verify that it is 5-connected.

[FIGURES 1-2 OMITTED]

It is easy to see that [d.sup.*] (x, y) = k + 2 in [Q.sub.k]. 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 [Q.sub.k] + xy is obtained whose crossing number is 11.

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 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 [Q.sub.k] in Figure 2. In Figure 4, an optimum drawing of [G.sub.0] + 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.

[FIGURES 3-4 OMITTED]

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 [G.sub.0], 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.

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 [G.sub.0] + xy if [G.sub.0] 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. Szekely, I. Vrt'o, Crossing numbers: bounds and applications. Intuitive geometry (Budapest, 1995), 179-206, J. Bolyai Math. Soc., Budapest, 1997.

[9] L.A. Szekely, 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

Bojan Mohar

Faculty of Mathematics and Physics

Department of Mathematics

University of Ljubijana

Jadranska 19

1000 Ljubljana, Slovenia

E-mail: bojan.mohar@uni-lj.si

Received: May 8, 2005

Printer friendly Cite/link Email Feedback | |

Author: | Mohar, Bojan |
---|---|

Publication: | Informatica |

Geographic Code: | 4EXSL |

Date: | Oct 1, 2006 |

Words: | 1971 |

Previous Article: | The spectra of Knodel graphs. |

Next Article: | Unsupervised feature extraction for time series clustering using orthogonal wavelet transform. |

Topics: |