Computing Labeled Orthogonal Drawings

Binucci, Carla and Didimo, Walter and Liotta, Giuseppe and Nonato, Maddalena (2002) Computing Labeled Orthogonal Drawings. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002 , pp. 66-73(Official URL:

Full text not available from this repository.


This paper studies the problem of computing labeled orthogonal drawings. A label is modeled as a rectangle of prescribed size and it can be associated with either a vertex or an edge. Several optimization goals are taken into account. Namely, the labeled drawing can be required to have minimum total edge length, minimum width, minimum height, or minimum area. We present ILP models to compute optimal drawings with respect to the first three objectives and an algorithm exploiting these models which computes a drawing of minimum area (the compaction problem is known to be NP-complete in general).

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_7
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.630 Labeling
P Styles > P.600 Poly-line > P.600.700 Orthogonal

Actions (login required)

View Item View Item