chai and assert should be used.

Every existing solution (including author solution), except one, can't actually solve the kata under the worst bounds: at least one of the inputs

!!!!!!!!!!!!!!!!!!!!!!
#%&()*+,-./0123456789:
!!!!!!!!!!!!!!!!!!!!!!
;<=>?@ABCDEFGHIJKLMNOP
!!!!!!!!!!!!!!!!!!!!!!
QRSTUVWXYZ[]^_abcdefgh
!!!!!!!!!!!!!!!!!!!!!!
ijklmnopqrstuvwxyz{|}$

!!!!!!!!!!!!!!!!!!!!!!
##%%&&(())**++,,--..//
0112233445566778899::0
!!!!!!!!!!!!!!!!!!!!!!
;;<<==>>??@@AABBCCDDEE
FGGHHIIJJKKLLMMNNOOPPF
!!!!!!!!!!!!!!!!!!!!!!
QQRRSSTTUUVVWWXXYYZZ[[
]^^__aabbccddeeffgghh]
!!!!!!!!!!!!!!!!!!!!!!
iijjkkllmmnnooppqqrrss
tuuvvwwxxyyzz{{||}}$$t

times out all these solutions, so clearly there needs to be more tests of maximal planar graphs. Also:

There are about 50 fixed tests and 1000 random tests

There are actually 1200 random tests. Since you do get to decide how many random tests to run, this should be an exact number, and definitely not an under-estimate.

The cheese mentioned below still works, after hardcoding all the fixed tests.

Leading and trailing newlines are inconsistent through the test cases; sometimes there are leading newline and sometimes not.