One- and two-page crossing numbers for some types of graphs

Abstract

The simplest graph drawing method is that of putting the vertices of a graph on a line (spine) and drawing the edges as half-circles on k half planes (pages). Such drawings are called k-page book drawings and the minimal number of edge crossings in such a drawing is called the k-page crossing number. In a one-page book drawing, all edges are placed on one side of the spine, and in a two-page book drawing all edges are placed either above or below the spine. The one- and two-page crossing numbers of a graph provide upper bounds for the standard planar crossing. In this paper, we derive the exact one-page crossing numbers for four-row meshes, present a new proof for the one-page crossing numbers of Halin graphs, and derive the exact two-page crossing numbers for circulant graphs . We also give explicit constructions of the optimal drawings for each kind of graph.

Keywords:

• book drawings
• one-page crossing number
• two-page crossing number
• four-row meshes
• Halin graphs
• circulant graphs

2000 AMS Subject Classifications :

• 05C10
• 05C45
• 05C60
• 05C62
• 05C75

Acknowledgements

This research was done while the first author was at the Department of Computer Science, Loughborough University, supported by the EPSRC grant GR/S76694/01.