Drawing Graphs with Orthogonal Crossings

Abstract

By a poly-line drawing of a graph G on n vertices we understand a drawing of G in the plane such that each edge is represented by a polygonal arc joining its two respective vertices. We call a turning point of a polygonal arc the bend. We consider the class of graphs that admit a poly-line drawing, in which each edge has at most one bend (resp. two bends) and any two edges can cross only at a right angle. It is shown that the number of edges of such graphs is at most O(n) (resp. O(n \log^2 n)). This is a strengthening of a recent result of Didimo et al.

8 pages, 5 figures