We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Almost all string graphs are intersection graphs of plane convex sets

Formale Metadaten

Titel
Almost all string graphs are intersection graphs of plane convex sets
Serientitel
Anzahl der Teile
21
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
A {\em string graph} is the intersection graph of a family of continuous arcs in the plane. 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 (n→∞). As a corollary, we obtain that {\em almost all} string graphs on n vertices are intersection graphs of plane convex sets.