On the additivity of crossing numbers of graphs Article uri icon

abstract

  • We describe a relationship between the crossing number of a graph G with a 2-edge-cut C and the crossing numbers of the components of G-C. Let G be a connected graph with a 2-edge-cut C := [V1,V2]. Let u 1u2, v1v2 be the edges of C, so that ui,vi ∈ Vi for i = 1,2, and let G i := G[Vi] and G%27i := Gi %2b u ivi. We show that if either G1 or G2 is not connected, then cr(G) = cr(G1) %2b cr(G2), and that if they are both connected then cr(G) = cr(G%271) %2b cr(G%272). We use this to show how to decompose crossing-critical graphs with 2-edge-cuts into smaller, 3-edge-connected crossing-critical graphs. We also observe that this settles a question arising from knot theory, raised by Sawollek, by describing exactly under which conditions the crossing number of the connected sum of two graphs equals the sum of the crossing numbers of the individual graphs. © 2008 World Scientific Publishing Company.
  • We describe a relationship between the crossing number of a graph G with a 2-edge-cut C and the crossing numbers of the components of G-C. Let G be a connected graph with a 2-edge-cut C := [V1,V2]. Let u 1u2, v1v2 be the edges of C, so that ui,vi ∈ Vi for i = 1,2, and let G i := G[Vi] and G'i := Gi %2b u ivi. We show that if either G1 or G2 is not connected, then cr(G) = cr(G1) %2b cr(G2), and that if they are both connected then cr(G) = cr(G'1) %2b cr(G'2). We use this to show how to decompose crossing-critical graphs with 2-edge-cuts into smaller, 3-edge-connected crossing-critical graphs. We also observe that this settles a question arising from knot theory, raised by Sawollek, by describing exactly under which conditions the crossing number of the connected sum of two graphs equals the sum of the crossing numbers of the individual graphs. © 2008 World Scientific Publishing Company.

publication date

  • 2008-01-01