- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Almost all string graphs are intersection graphs of...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Almost all string graphs are intersection graphs of plane convex sets Yuditsky, Lena
Description
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\rightarrow\infty$). As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets. This is a joint work with Janos Pach and Bruce Reed.
Item Metadata
Title |
Almost all string graphs are intersection graphs of plane convex sets
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2018-02-08T15:46
|
Description |
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\rightarrow\infty$). As a corollary, we obtain that {\em almost all} string graphs on $n$ vertices are intersection graphs of plane convex sets.
This is a joint work with Janos Pach and Bruce Reed.
|
Extent |
31 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Karlsruhe institute of technology (KIT)
|
Series | |
Date Available |
2018-08-08
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0369744
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International