On the Complexity of Some Geometric Problems With Fixed Parameters
The following graph-drawing problems are known to be complete for the existential theory of the reals (R -complete) as long as the parameter k is unbounded. Do they remain R -complete for a fixed value k? Do k graphs on a shared vertex set have a simultaneous geometric embedding? Is G a segment intersection graph, where G has maximum degree at most k? Given a graph G with a rotation system and maximum degree at most k, does G have a straight-line drawing which realizes the rotation system? We show that these, and some related, problems remain R -complete for constant k, where k is in the double or triple digits. To obtain these results we establish a new variant of Mnëv's universality theorem, in which the gadgets are placed so as to interact minimally; this variant leads to fixed values for k, where the traditional variants of the universality theorem require unbounded values of k., number=1, journal=Journal of Graph Algorithms and Applications, author=Schaefer, Marcus, year=2021, month=Jan., pages=195–218