Almost all string graphs are intersection graphs of plane convex sets

DOI10.1007/S00454-020-00213-ZMaRDI QIDQ2189736zbMATH OpenOpenAlexFDO

Authors Yanyan Li

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, https://drops.dagstuhl.de/opus/volltexte/2018/8781/

zbMATH Keywords

intersection graphsstring graphsstructure of a typical graph in a hereditary property

Mathematics Subject Classification ID

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)

Abstract: A {em string graph} is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of {em almost all} string graphs on $n$ vertices can be partitioned into {em five} cliques such that some pair of them is not connected by any edge ($nightarrowinfty$). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that {em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets.

Recommendations

• Almost all string graphs are intersection graphs of plane convex sets
• A separator theorem for string graphs and its applications
• A Separator Theorem for String Graphs and Its Applications
• scientific article; zbMATH DE number 3981198
• On string graph limits and the structure of a typical string graph

Cites work

• Almost all Berge Graphs are Perfect
• Decidability of string graphs
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs. II: Extremal graphs
• Excluding induced subgraphs: critical graphs
• Excluding induced subgraphs: quadrilaterals
• Forbidding induced even cycles in a graph: typical structure and counting
• How many ways can one draw a graph?
• scientific article; zbMATH DE number 3557819 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• On intersection representations of co-planar graphs
• On string graph limits and the structure of a typical string graph
• On the entropy values of hereditary classes of graphs
• Projections of Bodies and Hereditary Properties of Hypergraphs
• Recognizing string graphs in NP
• String graphs requiring exponential representations
• String graphs. II: Recognizing string graphs is NP-hard
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The fine structure of octahedron-free graphs
• The number of graphs without forbidden subgraphs
• The structure of almost all graphs in a hereditary property
• The typical structure of graphs without given excluded subgraphs
• Topology of Thin Film RC Circuits
• Toward a theory of crossing numbers
• Über wesentlich unplättbare Kurven im dreidimensionalen Raume

Cited in

(5)

• A sharp threshold phenomenon in string graphs
• On string graph limits and the structure of a typical string graph
• Almost all string graphs are intersection graphs of plane convex sets
• Intersection graphs of maximal sub-polygons of \(k\)-lizards
• Enumeration of interval graphs and d-representable complexes

This page was built for publication: Almost all string graphs are intersection graphs of plane convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189736)