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.     

A Fixed-Parameter Approach to 2-Layer Planarization

A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k · 6^k + |G|) time and the 1-Layer Planarization problem in O(3^k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.