Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-071 | 8th May 2026 11:38

Planarizing Gadgets for $(k,l)$-tight Graphs Do Not Exist

RSS-Feed




TR26-071
Authors: Archit Chauhan, Rohit Gurjar, Kilian Rothmund, Thomas Thierauf
Publication: 10th May 2026 15:19
Downloads: 23
Keywords: 


Abstract:

The problem of recognizing $(k,l)$-tight graphs is a fundamental problem that has close connections to well studied problems
like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic
NC-algorithms for the problem are known for planar graphs, but no such algorithm is known for general graphs.
A common approach to reduce a graph problem to the planar case is to use planarizing gadgets.
Our main contribution is to show that, unconditionally, planarizing gadgets for the problem of recognizing $(k,l)$-tight graphs do not exist.



ISSN 1433-8092 | Imprint