License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.65
URN: urn:nbn:de:0030-drops-122236
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12223/
Go to the corresponding LIPIcs Volume Portal

Raz, Orit E. ; Solymosi, József

Dense Graphs Have Rigid Parts

pdf-format:
LIPIcs-SoCG-2020-65.pdf (0.5 MB)

Abstract

While the problem of determining whether an embedding of a graph G in ℝ² is infinitesimally rigid is well understood, specifying whether a given embedding of G is rigid or not is still a hard task that usually requires ad hoc arguments. In this paper, we show that every embedding (not necessarily generic) of a dense enough graph (concretely, a graph with at least C₀n^{3/2}(log n)^β edges, for some absolute constants C₀>0 and β), which satisfies some very mild general position requirements (no three vertices of G are embedded to a common line), must have a subframework of size at least three which is rigid. For the proof we use a connection, established in Raz [Discrete Comput. Geom., 2017], between the notion of graph rigidity and configurations of lines in ℝ³. This connection allows us to use properties of line configurations established in Guth and Katz [Annals Math., 2015]. In fact, our proof requires an extended version of Guth and Katz result; the extension we need is proved by János Kollár in an Appendix to our paper.
We do not know whether our assumption on the number of edges being Ω(n^{3/2}log n) is tight, and we provide a construction that shows that requiring Ω(n log n) edges is necessary.

BibTeX - Entry

@InProceedings{raz_et_al:LIPIcs:2020:12223,
  author =	{Orit E. Raz and J{\'o}zsef Solymosi},
  title =	{{Dense Graphs Have Rigid Parts}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{65:1--65:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12223},
  URN =		{urn:nbn:de:0030-drops-122236},
  doi =		{10.4230/LIPIcs.SoCG.2020.65},
  annote =	{Keywords: Graph rigidity, line configurations in 3D}
}

Keywords: Graph rigidity, line configurations in 3D
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI