Graph Drawing - Quality Measures

Quality Measures

Many different quality measures have been defined for graph drawings, in an attempt to find objective means of evaluating their aesthetics and usability. In addition to guiding the choice between different layout methods for the same graph, some layout methods attempt to directly optimize these measures.

  • The crossing number of a drawing is the number of pairs of edges that cross each other. If the graph is planar, then it is often convenient to draw it without any edge intersections; that is, in this case, a graph drawing represents a graph embedding. However, nonplanar graphs frequently arise in applications, so graph drawing algorithms must generally allow for edge crossings.
  • The area of a drawing is the size of its smallest bounding box, relative to the closest distance between any two vertices. Drawings with smaller area are generally preferable to those with larger area, because they allow the features of the drawing to be shown at greater size and therefore more legibly. The aspect ratio of the bounding box may also be important.
  • Symmetry display is the problem of finding symmetry groups within a given graph, and finding a drawing that displays as much of the symmetry as possible. Some layout methods automatically lead to symmetric drawings; alternatively, some drawing methods start by finding symmetries in the input graph and using them to construct a drawing.
  • It is important that edges have shapes that are as simple as possible, to make it easier for the eye to follow them. In polyline drawings, the complexity of an edge may be measured by its number of bends, and many methods aim to provide drawings with few total bends or few bends per edge. Similarly for spline curves the complexity of an edge may be measured by the number of control points on the edge.
  • Several commonly used quality measures concern lengths of edges: it is generally desirable to minimize the total length of the edges as well as the maximum length of any edge. Additionally, it may be preferable for the lengths of edges to be uniform rather than highly varied.
  • Angular resolution is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high degree then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree.
  • The slope number of a graph is the minimum number of distinct edge slopes needed in a drawing with straight line segment edges (allowing crossings). Cubic graphs have slope number at most four, but graphs of degree five may have unbounded slope number; it remains open whether the slope number of degree-4 graphs is bounded.

Read more about this topic:  Graph Drawing

Other articles related to "quality, quality measures, measures":

Path Quality Analysis
... Path quality analysis In a communications path, an analysis that (a) includes the overall evaluation of the component quality measures, the individual link quality ...
Education In Lower Dir District - Quality Measures
... The term Quality Education needs clarity and no such practices are observed in the schools ... The PTAs are formed in the schools according to government procedures, but these are only limited to school petty repairs and not involved in the school management ...
Initiatives in Patient Safety - Pay For Performance (P4P) - United States
... initiatives in offices, clinics and hospitals, seeking to improving quality and avoid unnecessary health care costs ... Participating practices will phase in quality standards for preventive care and the management of common chronic illnesses such as diabetes ... Congress in 2006 showed that the model rewarded high quality, efficient provision of health care, but the lack of up-front payment for the investment in new systems of case management "have made for an ...
Electronic Health Record - National Contexts - United States - Meaningful Use
... electronic exchange of health information to improve quality of health care ... The use of certified EHR technology to submit clinical quality and other measures ... show they're using certified EHR technology in ways that can be measured significantly in quality and in quantity ...

Famous quotes containing the words measures and/or quality:

    One encounters very capable fathers abashed by their piano-playing daughters. Three measures of Schumann make them red with embarrassment.
    Alfred Döblin (1878–1957)

    The quality of decision is like the well-timed swoop of a falcon which enables it to strike and destroy its victim.
    Sun Tzu (6–5th century B.C.)