1 Search Results for "Solymosi, József"

Document

DOI: 10.4230/LIPIcs.SoCG.2020.65

Dense Graphs Have Rigid Parts

Authors: Orit E. Raz and József Solymosi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

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.

Cite as

Orit E. Raz and József Solymosi. Dense Graphs Have Rigid Parts. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SoCG.2020.65,
  author =	{Raz, Orit E. and Solymosi, J\'{o}zsef},
  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 =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.65},
  URN =		{urn:nbn:de:0030-drops-122236},
  doi =		{10.4230/LIPIcs.SoCG.2020.65},
  annote =	{Keywords: Graph rigidity, line configurations in 3D}
}

Refine by Author
1 Raz, Orit E.
1 Solymosi, József

Refine by Classification
1 Mathematics of computing → Combinatoric problems
1 Mathematics of computing → Graph theory

Refine by Keyword
1 Graph rigidity
1 line configurations in 3D

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Solymosi, József"

Dense Graphs Have Rigid Parts

Abstract

Cite as

Thanks for your feedback!

Could not send message