## 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:

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:

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?