DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.49

2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Authors: Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC.

Cite as

Rohit Gurjar, Kilian Rothmund, and Thomas Thierauf. 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.STACS.2026.49,
  author =	{Gurjar, Rohit and Rothmund, Kilian and Thierauf, Thomas},
  title =	{{2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.49},
  URN =		{urn:nbn:de:0030-drops-255385},
  doi =		{10.4230/LIPIcs.STACS.2026.49},
  annote =	{Keywords: Graph Rigidity, Parallel Algorithms, Polynomial Identity Testing, Derandomization}
}

Document

DOI: 10.4230/DagRep.14.9.104

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381)

Authors: Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, Jacobo Torán, and Kilian Rothmund

Published in: Dagstuhl Reports, Volume 14, Issue 9 (2025)

Abstract

Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The algebraic theme continues to play a central role in some of the most exciting recent progress in computational complexity in areas like circuit complexity, polynomial identity testing, pseudorandomness and derandomization, or error correcting codes. Beside algebraic methods, analytic methods like Fourier analysis have been used for quite some time in theoretical computer science. These methods have been used recently in some breakthrough results in complexity theory in areas like hardness of approximation, quantum computation, and scaling algorithms. A new theme that has gained importance in the last years is the area of meta-complexity, that is, the complexity of computational problems that are themselves problems about the complexity of computation. Meta-complexity provides a link between a variety of important areas like circuit complexity, proof complexity, cryptography, and learning theory. These new directions were in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 22371. Taking the recent exciting developments outlined above into account, we also included analytic methods this time. This Dagstuhl Seminar aimed to capitalize on recent progress and brought together researchers who are using a diverse array of algebraic and analytic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and we hope that this seminar has contributed in educating a diverse community about the latest new techniques.

Cite as

Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, Jacobo Torán, and Kilian Rothmund. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381). In Dagstuhl Reports, Volume 14, Issue 9, pp. 104-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{blaser_et_al:DagRep.14.9.104,
  author =	{Bl\"{a}ser, Markus and Saraf, Shubhangi and Shaltiel, Ronen and Tor\'{a}n, Jacobo and Rothmund, Kilian},
  title =	{{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381)}},
  pages =	{104--126},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{14},
  number =	{9},
  editor =	{Bl\"{a}ser, Markus and Saraf, Shubhangi and Shaltiel, Ronen and Tor\'{a}n, Jacobo and Rothmund, Kilian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.9.104},
  URN =		{urn:nbn:de:0030-drops-226065},
  doi =		{10.4230/DagRep.14.9.104},
  annote =	{Keywords: Algebraic complexity theory, circuit complexity, pseudorandomnes and derandomization, error correcting codes}
}

Search Results

Documents authored by Rothmund, Kilian

2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

Abstract

Cite as

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 24381)

Abstract

Cite as

Thanks for your feedback!

Could not send message