String graphs. I: The number of critical nonstring graphs is infinite
type: Item
instance of: scholarly article
title: String graphs. I: The number of critical nonstring graphs is infinite
zbMATH Open document ID: 0675.05058
DOI: 10.1016/0095-8956(91)90090-7
author: Jan Kratochvíl
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4105013
zbMATH Keywords: String graphs
zbMATH Keywords: intersection graphs
zbMATH Keywords: curves
zbMATH Keywords: induced minor
zbMATH Keywords: critical nonstring graphs
MaRDI profile type: MaRDI publication profile
full work available at URL: 0095-8956(91)90090-7
OpenAlex ID: W1983826065
cites work: Intersection graphs of curves in the plane
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Comparability graphs and intersection graphs
cites work: Energy, central charge, and the BPS bound for \(1+1\)-dimensional supersymmetric solitons
cites work: Q3309881
cites work: Q3745859
cites work: String graphs. II: Recognizing string graphs is NP-hard
cites work: Q3821580
cites work: Transitive Orientation of Graphs and Identification of Permutation Graphs
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
cites work: Topology of Thin Film RC Circuits
cites work: Weakly transitive orientations, Hasse diagrams and string graphs
Recommended article: String graphs. II: Recognizing string graphs is NP-hard
Recommended article: Recognizing string graphs in NP
Recommended article: Q3745859
Recommended article: Q3474685
Recommended article: The max clique problem in classes of string-graphs
description: scientific article; zbMATH DE number 4105013