2026-07-21T03:11:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8836 2024-03-06T10:42:45Z ddc:004 open_access

On the Size of Outer-String Representations Biedl, Therese Biniaz, Ahmad Derka, Martin string graph outer-string graph size of representation independent set Outer-string graphs, i.e., graphs that can be represented as intersection of curves in 2D, all of which end in the outer-face, have recently received much interest, especially since it was shown that the independent set problem can be solved efficiently in such graphs. However, the run-time for the independent set problem depends on N, the number of segments in an outer-string representation, rather than the number n of vertices of the graph. In this paper, we argue that for some outer-string graphs, N must be exponential in n. We also study some special string graphs, viz. monotone string graphs, and argue that for them N can be assumed to be polynomial in n. Finally we give an algorithm for independent set in so-called strip-grounded monotone outer-string graphs that is polynomial in n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Therese Biedl and Ahmad Biniaz and Martin Derka 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.10 urn:nbn:de:0030-drops-88360 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.10 eng https://creativecommons.org/licenses/by/3.0/legalcode