**Authors: **[tex2html_wrap4194]*P. Eades, S. Whitesides*

**Investigator username:** sue

**Category: ** perception

**Subcategory:** geometric algorithms

Given a bipartite graph G whose vertex set is partitioned into two sets A and B, it is common to draw the graph with the vertices of A on one line and the vertices of B on another line parallel to the first. Graph G is said to be biplanar if the vertices can be drawn on their respective lines so that none of the edges of G cross. We prove that determining whether G has a biplanar subgraph with at least K edges is NP-complete. This remains true when the positions of the vertices on one line are specified. The problem is solvable in polynomial time if the positions of all vertices are specified.

baron@cim.mcgill.ca