Tag Archives: Programming Languages

On Planarity of Control Flow Graphs

For our master’s project, we include visualisation of control flow graphs of Java bytecode as a user interface feature. When discussing the feature, a question quickly became apparent: are control flow graphs (CFG) planar? If so, we expect drawing them to be relatively easy. If not, however, we can abandon hope for being able to always draw nice graphs.

Obviously, unconditional jumps can cause arbitrarily nasty CFGs; that is not surprising as GOTOs are generally to be considered harmful. We agreed, however, that we should rather consider basic blocks of actual Java rather than arbitrary bytecode, as it is Java code we want to talk about. Sadly, even if we disregard labelled break just to be save, Java CFGs are not planar in general. The examples we found suggest that this is true for most procedural and object oriented languages, too. Read more »