Authors: [tex2html_wrap4194]P. Eades, S. Whitesides
Investigator username: sue
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.