*Result*: Maximum Bipartite Subgraphs of Geometric Intersection Graphs.

*We study the Maximum Bipartite Subgraph (M B S) 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 ′ ⊆ S such that the intersection graph of the objects in S ′ is bipartite. We first give an O (n 2) -time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the M B S problem is N P -hard on geometric graphs for which the maximum independent set is N P -hard (hence, it is N P -hard even on unit squares and unit disks). On the other hand, we give a P T A S 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 axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph (M T F S) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the M B S except the intersection graph induced by the set S ′ needs to be triangle-free only (instead of being bipartite). [ABSTRACT FROM AUTHOR]*