Unit Edge-Length Rectilinear Drawings with Crossings and Rectangular Faces

Abstract

Unit edge-length drawings, rectilinear drawings (where each edge is either a horizontal or a vertical segment), and rectangular face drawings are among the most studied subjects in Graph Drawing.  However, most of the literature on these topics refers to planar graphs and planar drawings. In this paper we study drawings with all the above nice properties but that allow edge crossings; we call them Unit Edge-length Rectilinear drawings with Rectangular Faces (UER-RF drawings). We consider crossings as dummy vertices and apply the unit edge-length convention to the edge segments connecting any two (real or dummy) vertices.  Note that  UER-RF drawings are grid drawings (vertices are placed at distinct integer coordinates), which is another classical requirement of graph visualizations. We present several efficient and easily implementable algorithms for recognizing graphs that admit UER-RF drawings and for constructing such drawings if they exist. We consider restrictions on the degree of the vertices or on the size of the faces. For each type of restriction, we consider both the general unconstrained setting and a setting in which either the external boundary of the drawing is fixed or the rotation system of the graph is fixed as part of the input.