Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Introduction. In 1963, Knuth published the first paper on a computer algorithm for a graph drawing problem, entitled “Computer-drawn Flowcharts” [8]. In this paper, Knuth describes an algorithm that takes as input an n-vertex directed graph G that represents a flowchart and, using the modern language of graph drawing, produces an orthogonal drawing of G. In Knuth’s algorithm, every vertex is given the same x-coordinate and every edge has at most O(1) bends, so that drawings produced using his algorithm can be output line-by-line on an (old-style) ASCII line printer and have worst-case area at most \(O(n^2)\). Some drawbacks of his approach are that his drawings can be highly non-planar, even if the graph G is planar, and his drawings can have very poor aspect ratios, since every vertex is drawn along a vertical line. Nevertheless, his drawings possess an additional desirable property that has not been specifically addressed since the time of his seminal paper, which we revisit in the present work.

Specifically, inspired by his drawing convention, we say that a directed orthogonal graph drawing is Knuthian if there is no vertex having an incident edge locally pointing upwards unless that vertex is a junction node, that is, a vertex having in-degree strictly greater than its out-degree. This property (rotated 180 degrees) is related to previously-studied concepts known as “upward” or “quasi-upward” drawing conventions [3–5], where all edges must locally enter a vertex from below and leave going up.

Our Results. In this poster, we announce efficient algorithms for producing Knuthian drawings of degree-three acyclic series-parallel directed graphs, that is, directed orthogonal drawings where vertices are represented as small rectangles or squares and edges are directed paths of horizontal and vertical segments. These are equivalent to the flowcharts of loop-free algorithms. We provide a recursive linear-time algorithm for producing such drawings of degree-three acyclic series-parallel digraphs and we show that such a graph with n vertices has a Knuthian drawing with width O(n) and height \(O(\log n)\). We then show how to “wrap” this drawing, while still maintaining it to be Knuthian, to fit within a fixed width, so that the area is \(O(n \log n)\) and the aspect ratio is constant. Our drawings strive to achieve few edge bends, both in the aggregate and per edge. Our drawing approach contrasts with previous approaches to drawing series-parallel graphs, including the standard recursive split-join-and-compose method and Knuth’s original method [8], as well as more recent methods for drawing series-parallel graphs (e.g., see [1, 2, 7]). For details, please see the full version of this paper [6].

Knuthian Drawings of Series-Parallel Flowcharts with \(O(n\log n)\) Area. We show that any n-vertex degree-three series-parallel graph has a Knuthian drawing with \(O(n \log n)\) area.

FormalPara Theorem 1

A degree-three series-parallel graph with n vertices has a Knuthian drawing with width O(n) and height \(O(\log n)\), such that each edge has at most two bends and the total number of bends is at most 1.25n.

Fixed-Width Drawings. We show how to adapt our \(O(n \log n)\)-area drawings, which admittedly have poor aspect ratios, so that they achieve constant aspect ratios, proving the following theorem.

FormalPara Theorem 2

A degree-three series-parallel graph with n nodes has a Knuthian drawing that can be produced in linear time to have width \(O(A + \log n)\) and height \(O((n/A)\log n)\), for any given \(A\ge \log n\); hence, the area is \(O(n \log n)\). The total number of bends is at most \(3.5n + o(n)\).

Experimental Results. We tested our Knuth drawing algorithm algorithm on some sample degree-three series-parallel graphs, based on two distributions used to create random binary series-parallel decomposition trees.