The recognition of beyond-planar graphs is mostly NP-hard, see
[1]}.
It has been expected that recognizing fan-crossing free graphs
is NP-complete, too, which has been stated as an open problem in
[1]} and is proved next.
