Minors and contraction

[gdalle]

trafficstars

It would be nice to have support for graph minors, at list for SimpleGraphs and possibly even in the interface by defining something like contract_edge!(g, s, d)

[gdalle]

@fieldofnodes

[etiennedeg]

There is merge_vertices(g, [s, d]) that does exactly what contract_edge would do (except it does not require an edge to contract). What really is lacking is a graph type with efficient mutations (and one efficient for edge contraction), and a little package with some functionality on graph minors could be a cool feature.

[fieldofnodes]

Awesome about merge_vertices.

A graph type could one dealing with minor properties. To this has anyone ever heard of SageMath? I have used this a few times when testing minors.

The premise to me is the result of Robertson-Seymour, where a class of graphs can be defined by the exclusion list. For example (and forgive if I am speaking down) all planar graphs can be defined by any graph that does not have K5 or K33 as a minor (Wagner and Kuratowski work).

The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions Graph minor.

Having this as a graph type could at least focus on the topological side.

[etiennedeg]

I'm well aware of the main results of graph minors, especially the Robertson-Seymour theorem. (which is in my tier 1 list of theorems) I'm not sure what is the graph type you are proposing? Minor operations can be done on any graph type (as long as it supports mutations). Would it have some additional structure, like a tree decomposition, or something? Or would it be a type to define graph classes that excludes minors?