On the Size of Outer-String Representations

No abstract is available for this paper.

• Publication year

  2018

• Venue

  Scandinavian Workshop on Algorithm Theory

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.SWAT.2018.10
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Restricted String Representations

  2017influential reference
• Refining the Hierarchies of Classes of Geometric Intersection Graphs

  2016cited by this paper
• Intersection Graphs of Rays and Grounded Segments

  2016cited by this paper
• Separators in region intersection graphs

  2016cited by this paper
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs

  2015cited by this paper
• An Algorithm for the Maximum Weight Independent Set Problem onOutersting Graphs

  2015influential reference
• Coloring intersection graphs of x-monotone curves in the plane

  2014cited by this paper
• Near-Optimal Separators in String Graphs

  2013cited by this paper
• Coloring intersection graphs of x-monotone curves in the plane

  2012cited by this paper
• Computing the independence number of intersection graphs

  2011cited by this paper
• Every planar graph is the intersection graph of segments in the plane: extended abstract

  2009cited by this paper
• A Separator Theorem for String Graphs and its Applications

  2009cited by this paper
• Separator theorems and Turán-type results for planar intersection graphs

  2008cited by this paper
• Independent set of intersection graphs of convex objects in 2D

  2004cited by this paper
• Recognizing string graphs in NP

  2002cited by this paper
• Recognizing String Graphs Is Decidable

  2001cited by this paper
• Decidability of string graphs

  2001cited by this paper
• Weakly transitive orientations, Hasse diagrams and string graphs

  1993cited by this paper
• The max clique problem in classes of string-graphs

  1992cited by this paper
• String graphs requiring exponential representations

  1991cited by this paper
• String graphs. II. recognizing string graphs is NP-hard

  1991cited by this paper
• The Hamiltonian Circuit Problem for Circle Graphs is NP-Complete

  1989cited by this paper
• The Complexity of Coloring Circular Arcs and Chords

  1980cited by this paper
• The Rectilinear Steiner Tree Problem is NP Complete

  1977cited by this paper
• Intersection graphs of curves in the plane

  1976cited by this paper
• Topology of thin film RC circuits

  1966cited by this paper

• Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations

  2025cites this paper
• Sparse Outerstring Graphs Have Logarithmic Treewidth

  2024cites this paper
• Constrained Outer-String Representations

  2024cites this paper
• Isometric path antichain covers: beyond hyperbolic graphs

  2023cites this paper
• Isometric Path Complexity of Graphs

  2022cites this paper
• Finding Geometric Representations of Apex Graphs is NP-Hard

  2021cites this paper