Orthogonal Drawings of Graphs with Vertex and Edge Labels

This paper studies the problem of computing orthogonal drawings of graphs with labels on vertices and edges. Our research is mainly motivated by Software Engineering and Information Systems domains, where tools like UML diagrams and ER-diagrams are considered fundamental for the design of sophisticated systems and/or complex data bases collecting enormous amount of information. A label is modeled as a rectangle of prescribed width and height and it can be associated with either a vertex or an edge. Our drawing algorithms guarantee no overlaps between labels, vertices, and edges and take advantage of the information about the set of labels to compute the geometry of the drawing. Several additional optimization goals are taken into account. Namely, the labeled drawing can be required to have either minimum total edge length, or minimum width, or minimum height, or minimum area among those preserving a given orthogonal representation. All these goals lead to NP-hard problems. We present MILP models to compute optimal drawings with respect to the first three goals and an exact algorithm that is based on these models to compute a labeled drawing of minimum area. We also present several heuristics for computing compact labeled orthogonal drawings and experimentally validate their performances, comparing their solutions against the optimum.