The problem of finding whether a given planar diagram of a graph, with over- and under-crossings, is a linkless embedding or not has unknown complexity (Kawarabayashi et al., 2010). My first question is, what about finding whether a given diagram is a flat embedding?
There is also interesting work showing how links and knots are "inevitable" in given graph projections, in the sense that any assignment of over- or under-crossings yields a knotted or linked graph embedding (Taniyama and Tatsuya, 1996). There's a wonderful graph-minor characterization of whether a given graph, with no fixed projection, has a linkless or flat embedding (Robertson et al., 1995). My second question is: have people attempted to design algorithms (even for specific cases or with bad complexity) to decide whether a given projection (without over- and under-crossings) can be given crossing information to yield a linkless or flat embedding?
Such an algorithm would seem hard to design at first, because it's already hard to recognize if a given diagram is linkless, but that doesn't seem to rule out an algorithm out for special classes of graphs because there may be "easy" linkless or flat embeddings to attain in those cases.
References
(Kawarabayashi et al., 2010) Kawarabayashi, Ken-ichi; Kreutzer, Stephan; Mohar, Bojan, Linkless and flat embeddings in 3-space and the unknot problem, Proceedings of the 26th annual symposium on computational geometry, SoCG 2010, Snowbird, UT, USA, June 13--16, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-0016-2). 97-106 (2010). ZBL1284.05174.
(Robertson et al., 1995) Robertson, Neil; Seymour, Paul; Thomas, Robin, Sachs’ linkless embedding conjecture, J. Comb. Theory, Ser. B 64, No. 2, 185-227 (1995). ZBL0832.05032.
(Taniyama and Tatsuya, 1996) Taniyama, Kouki; Tsukamoto, Tatsuya, Knot-inevitable projections of planar graphs, J. Knot Theory Ramifications 5, No. 6, 877-883 (1996). ZBL0876.57011.
