DRAWING GRAPHS IN 2 LAYERS

Let G = (U, L, E) be a bipartite graph with vertex set U or L and edge set E subset or equal-to U x L. A typical convention for drawing G is to put the vertices of U on a line and the vertices of L on a separat e, parallel line and then to represent edges by placing open straight line segments between the vertices that determine them. In this conven tion, a drawing is biplanar if edges do not cross, and a subgraph of G is biplanar if it has a biplanar drawing. The main results of this pa per are the following: (1) it is NP-complete to determine whether G ha s a biplanar subgraph with at least K edges; (2) it is also NP-complet e to determine whether G has such a subgraph when the positions for th e vertices in either U or L are specified; (3) when the positions of t he vertices in both U and L are specified, the problem can be solved i n polynomial time by transformation to the longest ascending subsequen ce problem.