I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?
Any ideas or referrences are appreciated, thank you in advance!
Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.
This paper shows that independent set is NP-complete for triangle-free planar graphs whose maximum degree is at most three (Theorem 2 with $\mathcal{F} = \{\triangle\}$). This is almost what you want (you want the graph to be 3-regular), and presumably with some work you could modify the proof to get exactly what you want.
Unfortunately Uehara's proof is wrong. If we consider planar subcubic graphs from Johnson's "Rectilinear Steiner Tree" paper then they could be disconnected and all this stuff with gadgets does not work. Also it does not lead to cubic ($3$-regular) planar graph: when replacing some vertex of degree 2 from the cycle around vertex of degree 1 with the gadget we again have some gadget vertex of degree 2 so the reduction process is infinite.
There is a Mohar's paper Face Covers and the Genus Problem for Apex Graphs that does contain correct proof of NP-hardness of MIS over 2-connected 3-regular planar graphs which involves Kratovchil superresult of NP-hardness of planar 3-connected 3-SAT. I suppose NP-hardness under your setting could be obtained by applying mentioned Mohar's result with Uehara's technique.
