1 Search Results for "Reed, Bruce"

Document
DOI: 10.4230/LIPIcs.SoCG.2018.68
Almost All String Graphs are Intersection Graphs of Plane Convex Sets

Authors: János Pach, Bruce Reed, and Yelena Yuditsky

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
A 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 almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge (n --> infty). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.
Cite as

János Pach, Bruce Reed, and Yelena Yuditsky. Almost All String Graphs are Intersection Graphs of Plane Convex Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2018.68,
  author =	{Pach, J\'{a}nos and Reed, Bruce and Yuditsky, Yelena},
  title =	{{Almost All String Graphs are Intersection Graphs of Plane Convex Sets}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.68},
  URN =		{urn:nbn:de:0030-drops-87818},
  doi =		{10.4230/LIPIcs.SoCG.2018.68},
  annote =	{Keywords: String graph, intersection graph, plane convex set}
}
  • Refine by Author
  • 1 Pach, János
  • 1 Reed, Bruce
  • 1 Yuditsky, Yelena

  • Refine by Classification

  • Refine by Keyword
  • 1 String graph
  • 1 intersection graph
  • 1 plane convex set

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact