Provable planarity of flowcharts

Question

I have a question: is there any reference (e.g. paper) with a proof of the planarity of flowchart layouts? Can anyone suggest an algorithm for generating flowchart (planar) layouts?

I know that there are some code-to-flowchart tools out there, but i'm unaware of their internals.

Answer 1

It depends on what you call a "flowchart". If the flowchart is the simple kind, ie. a directed graph where no node points upward (to a node that could have possibly been visited previously), then what you've described is a tree whose embedding in the plane is trivial.

If however your flowchart has loops (cycles) then it is simple to construct a counterexample, a graph that is not not embeddable in the plane. For a contrived example (as no restrictions were stated) consider the complete graph K5, in which every node is connected to every other. This graph is not planar.

As for drawing graphs, I'd like to recommend the excellent tool GraphViz which draws (among other things) beautiful flowcharts with automatic layout. You can choose a rendering engine that tries to preserve some order in your graph and there exists an explicit option for hierarchical graphs.

Answer 2

I disagree with Hooked. Flow charts, with some restrictions (using loops is NOT one of them), are planar. Some examples:

• A single primitive command translates to a planar graph (a single node)
• A sequence of statements: if the statements can be translated to planar graphs, the sequence can itself be translated to a planar graph (simply by connecting those subgraphs)
• A function: the same as above
• A (repeat-until, while-do, etc) loop is a sequence of statements that forms a cycle. Cycles are fine too, as long as they properly nest (and such constructs are designed to properly nest).
• Goto statements (goto, or break/continue/return statements that may jump) are not ok. If you have a nested loop, and from inside that you jump out of the outer loop, such an edge would clearly intersect the cycle (loop, function) that contains it. If the code is translated to exit one loop at a time, these are fine too. (This translation is not too different from simply introducing nodes to model the intersections).

There must be a more systematic way to formally prove that a flow-chart deriving from compositions of a particular set of constructs is planar, I wish I could think of it in 5 minutes, but no luck :)

update: By the way, gotos can trivially create a K3,3 or K5, for example this is a K5 (in good old-fashioned QBasic!):

00 GOTO (INT(RND * 5) * 10) 
10 GOTO (INT(RND * 5) * 10)
20 GOTO (INT(RND * 5) * 10)
30 GOTO (INT(RND * 5) * 10)
40 GOTO (INT(RND * 5) * 10)