String graphs. I: The number of critical nonstring graphs is infinite
String graphs (intersection graphs of curves in the plane) were originally studied in a connection with RC-circuits. The family of string graphs is closed in the induced minor order, and so it is reasonable to study critical nonstring graphs (nonstring graphs all proper induced minors of which are string graphs). The question whether there are infinitely many nonisomorphic critical nonstring graphs has been an open problem for some time. The main result of the paper settles this question. In a later paper of this series we show that recognizing string graphs is NP-hard.
scientific article; zbMATH DE number 4105013