Almost all string graphs are intersection graphs of plane convex sets
From MaRDI portal
Publication:2189736
DOI10.1007/s00454-020-00213-zzbMath1442.05189arXiv1803.06710OpenAlexW3033559598MaRDI QIDQ2189736
Publication date: 16 June 2020
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.06710
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)
Related Items (2)
Intersection graphs of maximal sub-polygons of \(k\)-lizards ⋮ A sharp threshold phenomenon in string graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The fine structure of octahedron-free graphs
- The structure of almost all graphs in a hereditary property
- Excluding induced subgraphs. II: Extremal graphs
- How many ways can one draw a graph?
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs requiring exponential representations
- On intersection representations of co-planar graphs
- Forbidding induced even cycles in a graph: typical structure and counting
- The number of graphs without forbidden subgraphs
- Decidability of string graphs
- On String Graph Limits and the Structure of a Typical String Graph
- Excluding induced subgraphs: Critical graphs
- The typical structure of graphs without given excluded subgraphs
- Excluding induced subgraphs: quadrilaterals
- Excluding Induced Subgraphs III: A General Asymptotic
- On the entropy values of hereditary classes of graphs
- Almost all Berge Graphs are Perfect
- Über wesentlich unplättbare Kurven im dreidimensionalen Raume
- Projections of Bodies and Hereditary Properties of Hypergraphs
- Topology of Thin Film RC Circuits
- Toward a theory of crossing numbers
- Recognizing string graphs in NP
This page was built for publication: Almost all string graphs are intersection graphs of plane convex sets
