# Distance-hereditary graphs, chord diagrams, and polyominoes

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.

The diagram below shows a polyomino whose dual chord diagram is bipartite, and has all interior faces quadrilaterals, but does not represent a bipartite distance-hereditary graph. Every bipartite distance-hereditary graph has either a vertex of degree one, or a pair of vertices with the same neighbor sets; but these would correspond in the polyomino to a square with only one neighbor, a square forming a bridge between two disconnected regions of the polyomino, or a 2×

The diagram below shows a polyomino whose dual chord diagram is bipartite, and has all interior faces quadrilaterals, but does not represent a bipartite distance-hereditary graph. Every bipartite distance-hereditary graph has either a vertex of degree one, or a pair of vertices with the same neighbor sets; but these would correspond in the polyomino to a square with only one neighbor, a square forming a bridge between two disconnected regions of the polyomino, or a 2×

*n*rectangle with two opposite sides that lie on the polyomino boundary. The polyomino shown below has none of these things. (A simpler example of a polyomino that does not come from a distance-hereditary graph is the heptomino formed by removing two opposite corners of a 3×3 grid of squares; the central square forms a bridge between two parts, but not one that corresponds to a degree-one vertex.)