• ## Celtix is NP-complete

Celtix is a puzzle recently developed by Andrew Taylor, in which one is given a rectangular array filled with thick diagonal lines that reflect off the walls of the rectangle to form a criss-crossing knotted pattern.

• Congratulations to Robert Hickingbotham a student of David Wood at Monash University who just finished his PhD with an impressive portfolio of research in graph structure theory. Next step: a post-doc at ENS Lyon.

• ## Teachable suffix tree construction

I often cover suffix trees in my algorithm and data structure classes, but until now haven’t generally covered the algorithms to build them. These are data structures describing the suffixes of a string (start at any position of the string and continue until the end), useful in many string algorithms.

• ## Congratulations, Dr. Khodabandeh!

‘Tis the season for dissertation defenses and candidacy exams, and my doctoral student Hadi Khodabandeh successfully defended his dissertation today.

• ## Congratulations, Dr. Ozel!

I participated today in the successful doctoral defense of Evrim Ozel, one of Mike Goodrich’s students at UCI. Evrim is Turkish, and came to UCI from Middle East Technical University in Ankara.

The Wikipedia article on perfect graphs is now a Good Article! Along the way, the reviewer asked me whether random graphs are likely to be perfect. I didn’t have a published source for that, so you won’t find it in the article. But as with most properties of random graphs, the answer depends how dense you want the graph to be. In the usual Erdős–Rényi–Gilbert $$G(n,p)$$ model of random graphs, we fix $$n$$ vertices and include each edge independently of the others with probability $$p$$. This turns out to have two phase transitions, between graphs that are likely to be perfect and graphs that are likely to be imperfect, one when the edge probability is $$\tfrac1n$$ and another when it is $$1-\tfrac1n$$. More precisely, if I’m not mistaken (which I could easily be):