Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.comgeo.2005.02.001 | Comput. Geom. |
Keywords | Field | DocType |
minimum width,edge label,labeling,optimal drawing,drawing algorithm,orthogonal representations,information systems domain,prescribed width,experimental analysis,compaction algorithms,graph drawing,orthogonal representation,minimum area,minimum height,orthogonal drawing,minimum total edge length,software engineering,complex data,information system,np hard problem | Graph drawing,Information system,Discrete mathematics,Combinatorics,Vertex (geometry),Exact algorithm,Unified Modeling Language,Rectangle,Algorithm,Complex data type,Heuristics,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 2 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
12 | 1.09 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carla Binucci | 1 | 103 | 16.18 |
| Walter Didimo | 2 | 943 | 76.56 |
| Giuseppe Liotta | 3 | 341 | 30.83 |
| Maddalena Nonato | 4 | 105 | 14.60 |