0xDE (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} 11011110) wrote,@ 2008-03-23 17:17:00 |
|
| Entry tags: | arrangements, chord diagrams, graph drawing |
Ageev's squaregraph
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:
