Orthogonal drawings and crossing numbers of the Kronecker product of two cycles

摘要

An orthogonal drawing of a graph is an embedding of the graph in the plane such that each edge is representable as a chain of alternately horizontal and vertical line segments. This style of drawing finds applications in areas such as optoelectronic systems, information visualization and VLSI circuits. We present orthogonal drawings of the Kronecker product of two cycles around vertex partitions of the graph into grids. In the process, we derive upper bounds on the crossing number of the graph. The resulting upper bounds are within a constant multiple of the lower bounds. Unlike the Cartesian product that is amenable to an inductive treatment, the Kronecker product entails a case-to-case analysis since the results depend heavily on the parameters corresponding to the lengths of the two cycles.