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.

Dynamic Binding

Consider the following snippet:

class A { void m() { ... } }
class B extends A { @Override void m() { ... } }
class C extends B { @Override void m() { ... } }

public class Main {
  static void m(A a) { a.m(); }
  static void n(A a) { a.m(); }
  static void o(A a) { a.m(); }

Due to dynamic binding, every call to A.m in Main might bind to any of the three implementations. In particular, this main method

public static void main(String[] args) {
    A a = new A(); B b = new B(); C c = new C();
    m(a); m(b); m(c);
    n(a); n(b); n(c);
    o(a); o(b); o(c);

implies this CFG:
Example Graph
In graph theory, a graph of this form is called the complete bipartite graph with three nodes on each side, in short \(K_{3,3}\). Now, a beautiful result due to Kuratowski states that any graph that has a subgraph homeomorphic to \(K_{3,3}\) is not planar. Therefore, any program that has at least three calls to a dynamically bound method with at least three implementations does not have a planar CFG; we imagine that this is the usual case in typical programs.

Multiple Returns

There is another way to create \(K_{3,3}\) without having to assume inheritance and dynamic binding. Have a look at method

void m(int i) {
  if ( i == 0 ) return; //#1
  if ( i == 1 ) return; //#2
  return;               //#3

together with a series of calls:

void n(int i) {
  m(i); do1();
  m(i); do2();
  m(i); do3();

Any program that calls n at least once with each of 0, 1 and another number will imply a CFG that has this one as a subgraph:
Example Graph
By the same reasoning as above, when this pattern occurs in a program its CFG can not be planar. As having only one return per method is not a wide-spread practise, this should be the usual case.

Open Questions

Above examples show that features common to typical state of the art programming languages render CFGs of many programs non-planar. What are other features that have this effect? Can we characterise language features that can safely be allowed? Are there combinations of features that together break planarity while subsets are safe? Does non-planarity imply complex programs, i.e. can the degree of planarity of a program’s CFG be used as a meaningful quality measure?


  1. w.r.t. using non-planarity as a sign of needless complexity:

    I think quite the opposite is true, that’s why polymorphism is such an essential feature in object oriented software design. When you call a method m(), (and you do it according to the Liskov Substitution Principle,) you can focus on the contract of the topmost implementation of m() you may possibly be calling, and forget about the rest.

    Also, maybe not all edges in the CFG are equally critical to cross. For instance, did you consider what happens when throwing an exception and crossing a finally clause? Drawing this as a CFG, you get multiple inputs into the finally block (one for each throw that happens in the try block), and you have a corresponding outgoing node for each.

    So the CFG node for the finally block has lots of inputs and lots of outputs. You can, however, duplicate this node in the CFG. When the control flow comes into that node for a specific exception type, it can only leave over the corresponding outgoing edge. So instead of exceptions E1, E2, E3 ingoing to Block B and outgoing exceptions E1, E2, E3, you could also have: exception E1 ingoing to Block B1 and outgoing exception E1; exception E2 ingoing to Block B2 and outgoing exception E2; etc.

    I’ve done this in my diploma thesis, too, but in a more direct fashion, as the purpose was a little different. You can find it on the Softech homepage, if you’re interested.