  We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as
follows. Given a set $S$ of $n$ geometric objects in the plane, we want to
compute a maximum-size subset $S'\subseteq S$ such that the intersection graph
of the objects in $S'$ is bipartite. We first give a simple $O(n)$-time
algorithm that solves the MBS problem on a set of $n$ intervals. We also give
an $O(n^2)$-time algorithm that computes a near-optimal solution for the
problem on circular-arc graphs. We show that the MBS problem is NP-hard on
geometric graphs for which the maximum independent set is NP-hard (hence, it is
NP-hard even on unit squares and unit disks). On the other hand, we give a PTAS
for the problem on unit squares and unit disks. Moreover, we show fast
approximation algorithms with small-constant factors for the problem on unit
squares, unit disks and unit-height rectangles. Finally, we study a closely
related geometric problem, called Maximum Triangle-free Subgraph (TFS), where
the objective is the same as that of MBS except the intersection graph induced
by the set $S'$ needs to be triangle-free only (instead of being bipartite).
