I have another preprint on the arXiv: “Combinatorics and geometry of finite and infinite squaregraphs” (arXiv:0905.4537), with Hans-Jürgen Bandelt and Victor Chepoi. It's a long one, 46 pages, and as the title says is about the properties of squaregraphs, planar graphs in which all the interior faces are quadrilaterals and all the interior vertices have degree at least four.

( Read more... )

Every distance-hereditary graph can be represented as a circle graph, the intersection graph of the chords of a chord diagram. And every bipartite distance-hereditary graph can be represented in this way by a chord diagram in which all interior faces of the arrangement formed by the chords are quadrilaterals. But the converse is not true.

( Read more... )

A. A. Ageev, in his paper "a triangle-free circle graph with chromatic number 5" [Discrete Math. 152: 295–298, 1996], constructed a chord diagram with 220 chords that needs five colors in any coloring for which crossing chords are given different colors; this is the maximum possible number of colors needed for any triangle-free chord diagram. The dual graph of Ageev's arrangement is a large squaregraph. Using the labeling scheme from my previous post together with some drawing algorithms from one of my papers, I was able to draw it, with each face drawn as a rhombus:

( Read more... )

Here's a simple way to label each of the regions of a triangle-free chord diagram by the indices of at most two of the chords.

( Read more... )

Back to chord diagrams.

( Read more... )

Draw a graph, having as its vertices the double permutations (sequences of two copies each of the numbers 0 through n − 1 such that the first copies of each number are in sorted order), and connect by an edge two sequences that differ by a single transposition of adjacent elements. What is the structure of this graph? I was naively expecting a 1×3×5×7... grid, coming from the enumeration of these objects as double factorials, but no.

( Read more... )

A chord diagram is formed by choosing some 2n points on a circle (say, at the vertices of a regular polygon) and then connecting them in pairs. It can be represented as a double permutation: a sequence of the 2n values 0,0,1,1,2,2,..., where each value appears twice, and where renumbering the values but keeping the same pairing forms a sequence that is considered to be equivalent. Simply place the values in clockwise order at the chosen points of the circle, and connect pairs of points with equal labels. For instance, the double permutation 0,0,1,2,3,1,3,2, placed clockwise starting at the top vertex of a regular octagon, produces the chord diagram

( Read more... )