{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:28:23Z","timestamp":1747189703027,"version":"3.40.5"},"reference-count":42,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03n04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p> We study the Maximum Bipartite Subgraph ([Formula: see text]) problem, which is defined as follows. Given a set [Formula: see text] of [Formula: see text] geometric objects in the plane, we want to compute a maximum-size subset [Formula: see text] such that the intersection graph of the objects in [Formula: see text] is bipartite. We first give an [Formula: see text]-time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the [Formula: see text] problem is [Formula: see text]-hard on geometric graphs for which the maximum independent set is [Formula: see text]-hard (hence, it is [Formula: see text]-hard even on unit squares and unit disks). On the other hand, we give a [Formula: see text] 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 ([Formula: see text]) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the [Formula: see text] except the intersection graph induced by the set [Formula: see text] needs to be triangle-free only (instead of being bipartite). <\/jats:p>","DOI":"10.1142\/s021819592350005x","type":"journal-article","created":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T03:11:55Z","timestamp":1702955515000},"page":"133-157","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Bipartite Subgraphs of Geometric Intersection Graphs"],"prefix":"10.1142","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7046-0091","authenticated-orcid":false,"given":"Satyabrata","family":"Jana","sequence":"first","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, 600113, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1274-4598","authenticated-orcid":false,"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, K1S 5B6, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0994-6428","authenticated-orcid":false,"given":"Saeed","family":"Mehrabi","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, K1S 5B6, Canada"}]},{"given":"Sasanka","family":"Roy","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, 700108, India"}]}],"member":"219","published-online":{"date-parts":[[2023,12,16]]},"reference":[{"key":"S021819592350005XBIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39881-1_14"},{"key":"S021819592350005XBIB003","doi-asserted-by":"publisher","DOI":"10.1137\/0210022"},{"key":"S021819592350005XBIB004","volume-title":"Computers and intractability","volume":"174","author":"Garey M. R.","year":"1979"},{"key":"S021819592350005XBIB005","first-page":"1","volume-title":"Proceedings Graph-Theoretic Concepts in Computer Science, 18th International Workshop","author":"Brandst\u00e4dt A.","year":"1992"},{"key":"S021819592350005XBIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050088"},{"key":"S021819592350005XBIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.10.006"},{"key":"S021819592350005XBIB008","doi-asserted-by":"publisher","DOI":"10.4236\/jcc.2016.48003"},{"key":"S021819592350005XBIB009","doi-asserted-by":"publisher","DOI":"10.1137\/0402004"},{"key":"S021819592350005XBIB010","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"},{"key":"S021819592350005XBIB011","doi-asserted-by":"publisher","DOI":"10.1137\/0204019"},{"key":"S021819592350005XBIB012","doi-asserted-by":"publisher","DOI":"10.1137\/0206007"},{"key":"S021819592350005XBIB013","doi-asserted-by":"publisher","DOI":"10.1137\/140980053"},{"key":"S021819592350005XBIB014","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90107-4"},{"key":"S021819592350005XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90079-9"},{"key":"S021819592350005XBIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"S021819592350005XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00294-8"},{"key":"S021819592350005XBIB019","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00536-w"},{"key":"S021819592350005XBIB020","doi-asserted-by":"publisher","DOI":"10.1137\/060650015"},{"key":"S021819592350005XBIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"S021819592350005XBIB023","first-page":"424","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS","author":"Lokshtanov D.","year":"2012"},{"key":"S021819592350005XBIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33293-7_4"},{"key":"S021819592350005XBIB025","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"S021819592350005XBIB026","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.97"},{"key":"S021819592350005XBIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24766-9_16"},{"key":"S021819592350005XBIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90023-5"},{"key":"S021819592350005XBIB029","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00288"},{"key":"S021819592350005XBIB030","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.77"},{"key":"S021819592350005XBIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00706-6"},{"key":"S021819592350005XBIB032","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.04.001"},{"key":"S021819592350005XBIB033","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"S021819592350005XBIB034","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.020"},{"key":"S021819592350005XBIB035","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00193-7"},{"issue":"1","key":"S021819592350005XBIB036","first-page":"85","volume":"31","author":"Kratochv\u00edl J.","year":"1990","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"S021819592350005XBIB037","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26626-8_46"},{"volume-title":"Monographs in Computer Science","year":"1999","author":"Downey R. G.","key":"S021819592350005XBIB038"},{"key":"S021819592350005XBIB039","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_41"},{"key":"S021819592350005XBIB040","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_14"},{"key":"S021819592350005XBIB041","doi-asserted-by":"publisher","DOI":"10.1137\/0209001"},{"key":"S021819592350005XBIB042","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.07.007"},{"key":"S021819592350005XBIB044","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.12.001"},{"key":"S021819592350005XBIB046","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00028-5"},{"key":"S021819592350005XBIB047","doi-asserted-by":"publisher","DOI":"10.1109\/81.414831"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819592350005X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T07:01:34Z","timestamp":1704438094000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S021819592350005X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":42,"journal-issue":{"issue":"03n04","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.1142\/S021819592350005X"],"URL":"https:\/\/doi.org\/10.1142\/s021819592350005x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2023,12]]}}}