Models and algorithms to compute orthogonal drawings of
Because of their readability, orthogonal drawings are widely used by applications. Examples incude: Data Flow diagrams, Entity-Relationship diagrams, drawings of relational schemas, ownership diagrams, computer networks, industrial diagrams, ecc.
Our expertise with respect to the orthogonal drawing standard spans
several decades and covers all the three basic steps of the so-called
topology-shape-metric approach. Namely:
- Planarization: we study algorithms to obtain planar embeddings of graphs, to handle constraints on the embeddings, to minimize the "depth" of the embeddings, etc. (see the "Planarity and Planar Graphs" topic for further details).
- Orthogonalization: we study algorithms to obtain orthogonal representations of graphs with the minimum number of bends. We consider both the case in which the embedding is fixed and the case in which the embedding can be changed, and both the case in which all the nodes have degree less or equal than four and the general case in which nodes can have an arbitrarily high degree.
- Compaction: we study the complexity of obtaining compact drawings of orthogonal representations. We study heuristics for the general case (which we proved to be NP-hard) and polynomial algorithms for specific families of graphs. We study how to handle constraints on the final drawings (for example, nodes with a prescribed size, user-specified entry points for the edges into the nodes, etc).
All this body of research has spurred the development of the GDToolkit library.