Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KILIAN ROTHMUND:
All reports by Author Kilian Rothmund:

TR25-103 | 16th July 2025
Rohit Gurjar, Kilian Rothmund, Thomas Thierauf

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

Minimally rigid graphs can be recognized 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 NC-algorithms to recognize whether one-crossing-minor-free graphs are minimally rigid. In the special case of $K_{3,3}$-free graphs, we also compute an infinitesimally ... more >>>




ISSN 1433-8092 | Imprint