At most single-bend embeddings of cubic graphs (Q1335404)

A graph is said to be single-bend embeddable if it has an embedding in the plane for which every edge consists of at most two horizontal or vertical line segments. (A bend is the intersection point of two line segments, one horizontal and the other vertical, whose union represents one edge.) It is shown that every cubic connected planar graph except \(K_ 4\) is single-bend embeddable. An \(O(n)\) amortized time algorithm is given for drawing a single-bend embeddable cubic graph of order \(n\). It is shown that the minimum total number of bends for a single-bend embeddable cubic graph of order \(n\) is at most \(n/2 + 1\); the result is best possible. This study has relevance to VLSI design.