{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the [[chromatic number]] of string graphs to be NP-hard.{{sfnp|Ehrlich|Even|Tarjan|1976}} {{harvtxt|Kratochvil|1991a}} foundobserved that [[Graph minor#Induced minors|induced minors]] of string graphs formare analso inducedstring minorgraphs. closedInduced class,minors butare notobtained from a minorgiven closedgraph classby ofcontracting graphs.edges Unlikeand fordeleting vertices; unlike the more general form of graph minor closedthey classes,do wherenot allow deleting edges. For graph minors, the [[Robertson–Seymour theorem]] states that thereany cangraph beproperty closed under minors onlyhas finitely many [[Forbidden graph characterization|minimal forbidden minors]]. However, this does not hold for induced minors, and Kratochvil found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvil|1991a}}
EveryAnalogously to the [[planar separator theorem]], every <math>m</math>-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of <math>O(m^{3/4}\log^{1/2}m)</math> vertices. It follows that the [[Biclique-free graph|biclique-free string graphs]], string graphs containing no <math>K_{t,t}</math> subgraph for some constant <math>t</math>, have <math>O(n)</math> edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|2016}}.</ref>
