On the biplanar crossing number

Abstract

In the design of printed and integrated circuits it is desirable to minimize the number of jumpers and via-holes. Linear graph theory provides apparatus useful in the formal specification and solution of this problem. Prior work has concentrated on the drawing of graphs in a single plane. This correspondence, however, is concerned with determining the minimum number of crossings for two subgraphs of a graph whose union is the entire graph. The two subgraphs correspond to the two sides of a printed circuit board or to two layers of metalization on an integrated circuit. An upper bound on this crossing number and a model yielding this bound have been found for complete graphs.