Graph drawing algorithms - I'm trying to render finite state automata

Question

I want to write something that will draw finite state automata. Does anyone know any algorithms that are related to this?

EDIT: I should mention that I know about graphviz. I want to build my own draw program/function, so what I'm looking for is some more theoretical stuff/pseudo-code for algorithms.

Answer 1

Graph drawing is a fairly complex subject due to the fact that different graphs need to be drawn in different ways - there is no one algorithm fits all approach.

May I suggest the following resource:

• http://cs.brown.edu/people/rtamassi/papers/gd-tutorial/gd-constraints.pdf

It should be a good starting point, page 15 provides a number of links and books to follow up.

Answer 2

To get started with graph drawing algorithms, see this famous paper:

• "A technique for drawing directed graphs" (1993), by Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, Kiem-phong Vo, IEEE Transactions on Software Engineering.

It describes the algorithm used by dot, a graphviz drawing program. On the linked page you will find many more references. You will also find some more papers when you google for "drawing directed graphs".

Also, you might find OpenFst convenient, a general toolkit for finite-state machines. It has a binary called fstdraw, which will output a finite-state machine in a format that can be read by dot.