License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.10
URN: urn:nbn:de:0030-drops-88360
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8836/
Go to the corresponding LIPIcs Volume Portal

Biedl, Therese ; Biniaz, Ahmad ; Derka, Martin

On the Size of Outer-String Representations

pdf-format:
LIPIcs-SWAT-2018-10.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{biedl_et_al:LIPIcs:2018:8836,
  author =	{Therese Biedl and Ahmad Biniaz and Martin Derka},
  title =	{{On the Size of Outer-String Representations}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8836},
  URN =		{urn:nbn:de:0030-drops-88360},
  doi =		{10.4230/LIPIcs.SWAT.2018.10},
  annote =	{Keywords: string graph, outer-string graph, size of representation, independent set}
}

Keywords: string graph, outer-string graph, size of representation, independent set
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI