0xDE ([info]11011110) wrote,
@ 2008-05-07 18:11:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Entry tags:chord diagrams, graph theory

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×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.)



(2 comments) - (Post a new comment)


[info]resnotebook.blogspot.com
2008-05-11 03:03 pm UTC (link)
Hi! You should probably fix your RSS. My Google reader is not showing any posts after this one.

(Reply to this) (Thread)


[info]11011110
2008-05-11 03:06 pm UTC (link)
Um, I don't have any posts after this one? I don't make a point of posting on a regular schedule. Or you mean it's not showing any before this one? In any case, the RSS is provided automatically by Livejournal; I have no control over it.

(Reply to this) (Parent)


(2 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…