[For the entire collection see Zbl 0527.00033.]
This paper treats and generalizes the classical graph-theoretical concept of homeomorphic containment: the graph G homeomorphically contains the graph G’ if G has a subgraph H into which G’ can be taken by replacing all the edges of G’ by paths having at most their endpoints in common. A finite set S of graphs is called a system of forbidden structures, and the set of graphs which do not homeomorphically contain any graph in S is called the language L(S) defined by S; for example, if \(S=\{K_ 5,K_{3,3}\}\) then by Kuratowski’s theorem L(S) is the set of planar graphs.
In F. Wankmüller [Lect. Notes Comput. Sci. 153, 405-414 (1983; Zbl 0519.68069)] and [U. Wiese, ”Das Wortproblem für Systeme verbotener Strukturen”, Diplomarbeit, Univ. Dortmund (1983)] the authors proved some properties of systems of forbidden structures and compared them with a special kind of graph grammar. Here, some of those results are summarized, some weaker versions of homeomorphic containment (in which the paths in H corresponding to the edges in G’ are no longer required to have at most their endpoints in common) are considered, and some further properties of systems of forbidden structures are proved for both the standard and weakened versions of homeomorphic containment.
The system S of forbidden structures is called minimal if no system of smaller cardinality defines the same language as S. It is shown that S is minimal if and only if none of its members homeomorphically contain another, and that if two minimal systems define the same language they contain the same graphs (up to isomorphism). The following problems are shown to be decidable (here G is a given graph and S and S’ are given systems of forbidden structures): (1) Is \(G\in L(S)?\) (2) Is L(S)\(\subset L(S')?\) (3) Is \(L(S)=L(S')?\) (4) Is L(S) empty? (5) Is L(S) the set of all graphs? (6) Is L(S) minimal? The last of these problems and a special case of the first (does G homeomorphically contain G’?) are shown to be NP-complete.