Clique-Based Separators for Geometric Intersection Graphs

Simple item page
dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorde Berg, Marken_US
dc.contributor.authorKisfaludi-Bak, Sándoren_US
dc.contributor.authorMonemizadeh, Mortezaen_US
dc.contributor.authorTheocharous, Leonidasen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorProfessorship Kisfaludi-Bak Sándoren
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.organizationEindhoven University of Technologyen_US
dc.date.accessioned2023-08-11T07:21:16Z
dc.date.available2023-08-11T07:21:16Z
dc.date.issued2023-06en_US
dc.descriptionFunding Information: The work in this paper is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: © 2022, The Author(s).
dc.description.abstractLet F be a set of n objects in the plane and let G×(F) be its intersection graph. A balanced clique-based separator of G×(F) is a set S consisting of cliques whose removal partitions G×(F) into components of size at most δn, for some fixed constant δ< 1. The weight of a clique-based separator is defined as ∑ C∈Slog (| C| + 1). Recently De Berg et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if S consists of convex fat objects, then G×(F) admits a balanced clique-based separator of weight O(n). We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight O(n), which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n2 / 3log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(nlogn). (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n2 / 3log n). (iv) Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(n+rlog(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for Maximum Independent Set (and, hence, Vertex Cover), for Feedback Vertex Set, and for q-Coloring for constant q in these graph classes.en
dc.description.versionPeer revieweden
dc.format.extent27
dc.format.extent1652–1678
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationde Berg, M, Kisfaludi-Bak, S, Monemizadeh, M & Theocharous, L 2023, ' Clique-Based Separators for Geometric Intersection Graphs ', Algorithmica, vol. 85, no. 6, pp. 1652–1678 . https://doi.org/10.1007/s00453-022-01041-8en
dc.identifier.doi10.1007/s00453-022-01041-8en_US
dc.identifier.issn0178-4617
dc.identifier.issn1432-0541
dc.identifier.otherPURE UUID: 31347662-e3a1-437f-8bb1-6093990912e2en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/31347662-e3a1-437f-8bb1-6093990912e2en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85139908380&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/117587767/SCI_de_Berg_etal_Algorithmica_2023.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/122340
dc.identifier.urnURN:NBN:fi:aalto-202308114689
dc.language.isoenen
dc.publisherSpringer
dc.relation.ispartofseriesAlgorithmicaen
dc.relation.ispartofseriesVolume 85, issue 6en
dc.rightsopenAccessen
dc.subject.keywordComputational geometryen_US
dc.subject.keywordIntersection graphsen_US
dc.subject.keywordSeparator theoremsen_US
dc.titleClique-Based Separators for Geometric Intersection Graphsen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion
Files
Collections
[article-cris] Perustieteiden korkeakoulu / SCI