Orthogonal Drawings

Orthogonal Drawings

Topic home

Graph Drawing
 Topics
 Tools

Publications:
 By type
 By year

Orthogonal Drawings

    Models and algorithms to compute orthogonal drawings of graphs.

    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.