String graphs. I: The number of critical nonstring graphs is infinite (Q1121917)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4105013
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | String graphs. I: The number of critical nonstring graphs is infinite |
scientific article; zbMATH DE number 4105013 |
Statements
String graphs. I: The number of critical nonstring graphs is infinite (English)
0 references
1991
0 references
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.
0 references
String graphs
0 references
intersection graphs
0 references
curves
0 references
induced minor
0 references
critical nonstring graphs
0 references
0 references
0.9274638891220092
0 references
0.901042342185974
0 references
0.8503760695457458
0 references
