526
个编辑
更改
跳到导航
跳到搜索
第59行：
第59行： − 为了找到客观评价图形美观性和可用性的方法，已经定义了许多不同的图形质量度量方法。除了指导针对同一图形的不同布局方法之间的选择之外，某些布局方法还尝试直接优化这些度量。+ 第68行：
第68行： − + 第74行：
第74行： − + − 重要的是，边缘的形状要尽可能简单，以使眼睛更容易跟踪它们。在折线图中，一条边的复杂性可以通过它的弯曲数来衡量，许多方法的目的是提供很少的总弯曲或每条边很少弯曲的图。类似地，对于样条曲线，边的复杂性可以通过边上控制点的数量来度量。+ − + 第87行：
第87行： −
→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.
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.
为了找到客观评价图形美观性和可用性的方法，我们定义了许多不同的图形质量度量方法。除了用于指导对同一图形的不同布局方法之间的选择之外，某些布局方法还尝试直接优化这些度量。
[[File:4node-digraph-embed.svg|upright=0.5|thumb|
[[File:4node-digraph-embed.svg|upright=0.5|thumb|
*The [[Crossing number (graph theory)|crossing number]] of a drawing is the number of pairs of edges that cross each other. If the graph is [[planar graph|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.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p 14.</ref>
*The [[Crossing number (graph theory)|crossing number]] of a drawing is the number of pairs of edges that cross each other. If the graph is [[planar graph|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.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p 14.</ref>
图的'''<font color="#ff8000">交叉数 Crossing Number</font>'''是相互交叉的边对的数目。如果图形是平面的，那么通常可以方便地画出没有任何边缘相交的图形;也就是说，在本例中，图形绘制表示'''<font color="#ff8000">图形嵌入 Graph Embedding</font>'''。然而，应用中经常出现非平面图，因此图形绘制算法通常必须考虑边缘交叉。
图的'''<font color="#ff8000">交叉数 Crossing Number</font>'''是相交的成对的边的数目。如果图形是平面的，那么我们通常可以方便地画出没有任何边缘相交的图形;也就是说，在本例中，图形绘制表示'''<font color="#ff8000">图形嵌入 Graph Embedding</font>'''。然而，实际应用中经常出现非平面图，因此图形绘制算法通常必须考虑边缘交叉。
*The [[Area (graph drawing)|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.
*The [[Area (graph drawing)|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 [[Graph automorphism|symmetry group]]s 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.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p. 16.</ref>
*Symmetry display is the problem of finding [[Graph automorphism|symmetry group]]s 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.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p. 16.</ref>
对称显示的问题是在给定的图形中找到'''<font color="#ff8000">对称组 Symmetry Groups</font>'''，并找到尽可能多地显示对称的绘图。一些布局方法自动导致对称图形;另外，一些绘图方法从查找输入图形中的对称性开始，并使用它们来构造绘图。
对称显示的问题是在给定的图形中找到'''<font color="#ff8000">对称组 Symmetry Groups</font>'''，并找到尽可能多地显示对称的绘图。一些布局方法自动形成对称图形;另外，一些绘图方法从查找输入图形中的对称性开始，并使用它们来构造绘图。
*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 [[Bend minimization|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.
*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 [[Bend minimization|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.
*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 (graph drawing)|Angular resolution]] is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high [[degree (graph theory)|degree]] then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree.<ref name="ps09">{{harvtxt|Pach|Sharir|2009}}.</ref>
*[[Angular resolution (graph drawing)|Angular resolution]] is a measure of the sharpest angles in a graph drawing. If a graph has vertices with high [[degree (graph theory)|degree]] then it necessarily will have small angular resolution, but the angular resolution can be bounded below by a function of the degree.<ref name="ps09">{{harvtxt|Pach|Sharir|2009}}.</ref>
*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 graph]]s 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.<ref name="ps09"/>
*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 graph]]s 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.<ref name="ps09"/>
图的'''<font color="#ff8000">斜率数 Slope Number</font>'''是在具有直线段边(允许交叉)的图中所需的明显边缘斜率的最小值。'''<font color="#ff8000">三次图 Cubic Graphs</font>'''的斜率数最多为4，五次图的斜率数可能是无界的;4度图的斜率数是否有界仍然是开放的。
图的'''<font color="#ff8000">斜率数 Slope Number</font>'''是在具有直线段边(允许交叉)的图中所需的明显边缘斜率的最小值。'''<font color="#ff8000">三次图 Cubic Graphs</font>'''的斜率数最多为4，五次图的斜率数可能是无界的;4度图的斜率数是否有界仍然是开放的。
==Layout methods 布局方法==
==Layout methods 布局方法==