Crossing Number for Graphs with Bounded Pathwidth The crossing number is the smallest number of pairwise edge crossings when drawing a graph into the plane. There are only very few graph classes for which the exact crossing number is known or for which there at least exist constant approximation ratios. Furthermore, up to now, general crossing number computations have never been successfully tackled using bounded width of graph decompositions, like treewidth or pathwidth. In this paper, we show that the crossing number is tractable (even in linear time) for maximal graphs of bounded pathwidthxc2xa03. The technique also shows that the crossing number and the rectilinear (a.k.a. straightline) crossing number are identical for this graph class, and that we require only an O(n)times O(n)grid to achieve such a drawing. Our techniques can further be extended to devise a 2approximation for general graphs with pathwidth 3. One crucial ingredient here is that the crossing number of a graph with a separation pair can be lowerbounded using the crossing numbers of its cutcomponents, a result that may be interesting in its own right. Finally, we give a 4mathbfw3approximation of the crossing number for maximal graphs of pathwidthxc2xa0mathbfw. This is a constant approximation for bounded pathwidth. We complement this with an NPhardness proof of the weighted crossing number already for pathwidth 3 graphs and bicliques K_3,n.

On the Crossing Numbers of the Joining of a Specific Graph on Six Vertices with the Discrete Graph In the paper, we extend known results concerning crossing numbers of join products of small graphs of order six with discrete graphs. The crossing number of the join product      G *    D n      for the graph     G *     on six vertices consists of one vertex which is adjacent with three nonconsecutive vertices of the 5cycle. The proofs were based on the idea of establishing minimum values of crossings between two different subgraphs that cross the edges of the graph     G *     exactly once. These minimum symmetrical values are described in the individual symmetric tables.