Almost all string graphs are intersection graphs of plane convex sets
From MaRDI portal
Publication:5116528
DOI10.4230/LIPIcs.SoCG.2018.68zbMath1489.05120OpenAlexW2964212140MaRDI QIDQ5116528
No author found.
Publication date: 18 August 2020
Full work available at URL: https://arxiv.org/pdf/1803.06710.pdf
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)
Ordered graphs and large bi-cliques in intersection graphs of curves ⋮ Almost all string graphs are intersection graphs of plane convex sets
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
- 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 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
- Almost all string graphs are intersection graphs of plane convex sets
- 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