Some time ago I reposted a question from MathOverflow about whether graphs with many cycles have long cycles with doubled edges as minors. The answer turned out to be no, with a counterexample found by Anton Malyshev for a related question about paths and doubled-path minors. Malyshev’s graphs can be formed by starting from a pair of vertices (such as the central two vertices in the drawing below) and then repeatedly adding two more vertices adjacent to the two previously-added vertices:

32-vertex Malyshev graph

Lately I’ve been thinking about the same graphs again, because they have an interesting combination of properties:

  • They are planar, and 2-degenerate, and triangle-free, like the triangle-free penny graphs and the squaregraphs.

  • Unlike both of those other types of graphs, an \(n\)-vertex Malyshev graph has exactly \(2n-4\) edges, the maximum possible for a planar triangle-free graph.

  • They have high diameter, linear in the number of vertices.

  • They are bipartite, and are maximal among the planar bipartite graphs.

  • They are very far from being 3-connected, so if the vertices are labeled they have many distinct planar embeddings, showing that being maximal planar bipartite is very different from being maximal planar.

  • They have both bounded treewidth and bounded face size, like the nested triangles graph and the Apollonian networks but unlike many other planar graphs.

  • They are permutation graphs.

One way to see this last property is to recognize that the drawing above is exactly the form that one gets for a method of drawing planar bipartite permutation graphs that I described in an earlier post, and in fact to make this drawing I used the same program as the one that I used in that post.

Another way to see it is to find a permutation representation for these graphs. We want a sequence of permutation elements where each two elements are out-of-order with only the two ahead of them and the two behind them, like this:

A permutation representing the 32-vertex Malyshev graph

We can convert this to my notation for bipartite permutation graphs by scanning this picture from left to right, looking at the direction of the line segments at the top and bottom of the picture at each position in this scan, and recording that pair of directions by a character that slants in the same direction at its top and bottom. In this case, the result is the string “>>\\//\\//\\//\\//\\//\\//\\//<<”. And that’s what I gave my permutation-graph-drawing code as input, to get it to produce the top picture.

(Discussion on Google+)