Minors

[mtorpey]

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

— Wikipedia

I believe we don't have anything about minors in the package at the moment, and this might be a nice supplement to all the other concepts of "containment" of graphs (subdigraph, embedding, induced subdigraph, mono/epi/endomorphisms) which we already support.

One early decision would be how to handle direction, which doesn't seem to be established in the literature. Then perhaps we could consider some functions such as:

• IsDigraphMinor(super, sub)
• DigraphMinorMappings(super, sub)
• AllDigraphMinors(super)

Could be difficult computationally?

[james-d-mitchell]

Good suggestion @mtorpey, just to mention that there is some stuff related to minors in the planarity part of Digraphs.

[mtorpey]

I see there's some stuff in edge-addition-planarity-suite – do you suspect we could make more use of that library?

[james-d-mitchell]

There are the functions:

• SubdigraphHomeomorphicToK23
• SubdigraphHomeomorphicToK4
• SubdigraphHomeomorphicToK33

https://digraphs.github.io/Digraphs/doc/chap5_mj.html#X806D2D6B85E0B269

[mtorpey]

"homeomorphic" seems to mean something like "minor" here, but we should be careful to know exactly what it means. We should also be careful of definitions like "topological minor" and all the other variations of "Minor" that mean different things.