As you suggest, a lot of people have thought about this question. It's hard to find arrangements of an unknot that are convincingly hard to untie, but there are techniques
that do pretty well.
Have you ever had to untangle a marionette, especially one that a
toddler has played with? They tend to become entangled in a certain way, by a series of
operations where
the marionette twists so that two bundles of control strings are twisted in an opposite
sense, sometimes compounded with previous entanglements. It can take considerable
patience and close attention to get the mess undone. The best solution: don't give marionettes to young or inattentive children!
You can apply this to the
unknot, by first winding it up in a coil, then taking opposite sides of the coil and
braiding them (creating inverse braids on the two ends), then treating what you
have like a marionette to be tangled. Once the arrangement has a bit of complexity,
you can regroup it in another pattern (as two globs of stuff connected by $2n$ strands)
and do some more marionette type entanglement. In practice, unknots can become pretty
hard to undo.
As far as I can tell, the Kaufmann and Lambropoulou paper you cited deals is discussing various cases of this kind of marionette-tangling operation.
I think it's entirely possible that there's a polynomial-time combinatorial algorithm
to unknot an unknottable curve, but this has been a very hard question to resolve.
The minimum area of a disk that an unknot bounds grows exponentially in terms of
the complexity of an unknotted curve. However, such a disk can be described with
data that grows as a polynomial in terms of the number of crossings or similar measure, using normal surface theory. It's unknown (to me)
but plausible (to me) that unknotting can be done by an isotopy of
space that has a polynomially-bounded, perhaps linearly-bounded, "complexity", suitably
defined --- that is, things like the marionette untangling moves. This would not
imply you can find the isotopy easily---it just says the problem is in NP, which
is already known.
One point: the Smale Conjecture, proved by Allen Hatcher, says that the group of
diffeomorphisms of $S^3$ is homotopy equivalent to the subgroup $O(4)$. A corollary
of this is that the space of smooth unknotted curves retracts to the space of
great circles, i.e., there exists a way to isotope smooth unknotted curves to round circles that is continuous as a function of the curve.
The theory of knotted trees is obviously trivial. So given a knotted graph $\Gamma$, take a maximal tree in it and you can bring it to a standard form, say to be embedded as a planar object inside a tiny disk that is disjoint from the rest of the knotted graph; which is just the finitely many arcs that make the complement of the tree. But now you can draw $\Gamma$ in the plane so that "everything interesting" (namely, the complement of the tree) is outside of a small disk. Do inversion, and you have a fixed tree outside the disk and a tangle inside it. (Some details depend on whether your vertices are rigid or not, or "thickened" or not, but the conclusion is always more or less the same).
This correspondence between knotted graphs and tangles is not canonical - it depends on the (combinatorial) choice of a maximal tree, and modifying that choice modifies the resulting tangle (in simple ways that will not be stated here).
So topologically speaking, "knotted graphs" are not interesting. They are merely tangles, along with a bit of further combinatorial data (mostly the tree). If you totally understand the theory of tangles (modulo some simple to state actions, which also depend on what rigidity assumptions are made for the vertices), you'd totally understand knotted graphs.
Yet there's lot's of beautiful information in the interaction between the combinatorics of the graph and the topology of the tangle. For example, see my recent paper with Zsuzsanna Dancso, arXiv:1103.1896, in which we study the relationship between knotted trivalent graphs and Drinfel'd associators.
Best Answer
I saw two articles today (12/2/21) that reminded me of this post. I am mentioning them here to potentially help the OP: