第10行: |
第10行: |
| '''Graph drawing''' is an area of [[mathematics]] and [[computer science]] combining methods from [[geometric graph theory]] and [[information visualization]] to derive two-dimensional depictions of [[graph (discrete mathematics)|graph]]s arising from applications such as [[social network analysis]], [[cartography]], [[linguistics]], and [[bioinformatics]].<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, pp. vii–viii; {{harvtxt|Herman|Melançon|Marshall|2000}}, Section 1.1, "Typical Application Areas".</ref> | | '''Graph drawing''' is an area of [[mathematics]] and [[computer science]] combining methods from [[geometric graph theory]] and [[information visualization]] to derive two-dimensional depictions of [[graph (discrete mathematics)|graph]]s arising from applications such as [[social network analysis]], [[cartography]], [[linguistics]], and [[bioinformatics]].<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, pp. vii–viii; {{harvtxt|Herman|Melançon|Marshall|2000}}, Section 1.1, "Typical Application Areas".</ref> |
| | | |
− | Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics. | + | '''<font color="#ff8000">图的绘制 Graph Drawing</font>''' is an area of '''<font color="#ff8000">数学 Mathematics</font>''' and '''<font color="#ff8000">计算机科学 Computer Science</font>''' combining methods from '''<font color="#ff8000">几何图形理论 Geometric Graph Theory</font>'''and '''<font color="#ff8000">信息可视化 Information Visualization</font>''' to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics. |
| | | |
| 图形绘制是数学和计算机科学的一个交叉领域,它结合了几何图形理论和信息可视化的方法,对来自社会网络分析、制图学、语言学和生物信息学等各种应用场景进行二维描述。 | | 图形绘制是数学和计算机科学的一个交叉领域,它结合了几何图形理论和信息可视化的方法,对来自社会网络分析、制图学、语言学和生物信息学等各种应用场景进行二维描述。 |
第18行: |
第18行: |
| A drawing of a graph or '''network diagram''' is a pictorial representation of the [[vertex (graph theory)|vertices]] and [[edge (graph theory)|edges]] of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph.<ref name="dett6">{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p. 6.</ref> In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and [[aesthetics]].<ref name="dett-viii"/> The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map.<ref>{{harvtxt|Misue|Eades|Lai|Sugiyama|1995}}</ref> | | A drawing of a graph or '''network diagram''' is a pictorial representation of the [[vertex (graph theory)|vertices]] and [[edge (graph theory)|edges]] of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph.<ref name="dett6">{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, p. 6.</ref> In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and [[aesthetics]].<ref name="dett-viii"/> The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map.<ref>{{harvtxt|Misue|Eades|Lai|Sugiyama|1995}}</ref> |
| | | |
− | A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph. In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and aesthetics. | + | A drawing of a graph or network diagram is a pictorial representation of the vertices and edges of a graph. This drawing should not be confused with the graph itself: very different layouts can correspond to the same graph. In the abstract, all that matters is which pairs of vertices are connected by edges. In the concrete, however, the arrangement of these vertices and edges within a drawing affects its understandability, usability, fabrication cost, and aesthetics.The problem gets worse if the graph changes over time by adding and deleting edges (dynamic graph drawing) and the goal is to preserve the user's mental map. |
| | | |
− | 图形或网络图的绘制是通过从图形抽象出的顶点和边表示的。这个图不应与图形本身混淆: 非常不同的图可以对应于同一个图形。抽象地说,重要的是哪一对顶点是由边连在一起。然而,在具体的绘图中,这些顶点和边的排列影响了它的可理解性、可用性、制造成本和美学。
| + | 图形或'''<font color="#ff8000">网络图 Network Diagram</font>'''的绘制是通过从图形抽象出的顶点和边表示的。这个图不应与图形本身混淆: 非常不同的图可以对应于同一个图形。抽象地说,重要的是哪一对顶点是由边连在一起。然而,在具体的绘图中,这些顶点和边的排列影响了它的可理解性、可用性、制造成本和美学。如果图形通过添加和删除边缘(动态绘制图形)而随时间变化,并且目标是保存用户的心理映射,那么问题会变得更糟。 |
| | | |
| | | |
第35行: |
第35行: |
| Graphs are frequently drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as line segments, polylines, or curves in the Euclidean plane. Node–link diagrams can be traced back to the 13th century work of Ramon Llull, who drew diagrams of this type for complete graphs in order to analyze all pairwise combinations among sets of metaphysical concepts. | | Graphs are frequently drawn as node–link diagrams in which the vertices are represented as disks, boxes, or textual labels and the edges are represented as line segments, polylines, or curves in the Euclidean plane. Node–link diagrams can be traced back to the 13th century work of Ramon Llull, who drew diagrams of this type for complete graphs in order to analyze all pairwise combinations among sets of metaphysical concepts. |
| | | |
− | 图经常绘制成节点链接图,其中顶点可表示为圆盘、框或文本标签,边表示为欧几里德平面上的线段、折线或曲线。节点链接图可以追溯到13世纪雷蒙 · 卢尔的作品,他为得到完全图,绘制了这种类型的图,以便分析形而上学概念集合之间的所有成对组合。
| + | 图经常绘制成节点链接图,其中顶点可表示为圆盘、框或文本标签,边表示为'''<font color="#ff8000">欧几里德平面 Euclidean Plane</font>'''上的'''<font color="#ff8000">线段 Line Segments</font>'''、'''<font color="#ff8000">折线 Polylines</font>'''或曲线。节点链接图可以追溯到13世纪雷蒙 · 卢尔的作品,他为得到完全图,绘制了这种类型的图,以便分析形而上学概念集合之间的所有成对组合。 |
| | | |
| | | |
第43行: |
第43行: |
| In the case of directed graphs, arrowheads form a commonly used graphical convention to show their orientation; Upward planar drawing uses the convention that every edge is oriented from a lower vertex to a higher vertex, making arrowheads unnecessary. | | In the case of directed graphs, arrowheads form a commonly used graphical convention to show their orientation; Upward planar drawing uses the convention that every edge is oriented from a lower vertex to a higher vertex, making arrowheads unnecessary. |
| | | |
− | 在有向图的情况下,箭头约定俗成的来显示它们的方向; 向上的平面绘图使用以下约定:每个边都从较低的顶点定向到较高的顶点,因此不需要箭头。
| + | 在'''<font color="#ff8000">有向图 Directed Graphs</font>'''的情况下,'''<font color="#ff8000">箭头 Arrowheads</font>'''约定俗成的来显示它们的方向; '''<font color="#ff8000">向上平面绘图 Upward Planar Drawing</font>'''使用以下约定:每个边都从较低的顶点定向到较高的顶点,因此不需要箭头。 |
| | | |
| | | |
第51行: |
第51行: |
| Alternative conventions to node–link diagrams include adjacency representations such as circle packings, in which vertices are represented by disjoint regions in the plane and edges are represented by adjacencies between regions; intersection representations in which vertices are represented by non-disjoint geometric objects and edges are represented by their intersections; visibility representations in which vertices are represented by regions in the plane and edges are represented by regions that have an unobstructed line of sight to each other; confluent drawings, in which edges are represented as smooth curves within mathematical train tracks; fabrics, in which nodes are represented as horizontal lines and edges as vertical lines; and visualizations of the adjacency matrix of the graph. | | Alternative conventions to node–link diagrams include adjacency representations such as circle packings, in which vertices are represented by disjoint regions in the plane and edges are represented by adjacencies between regions; intersection representations in which vertices are represented by non-disjoint geometric objects and edges are represented by their intersections; visibility representations in which vertices are represented by regions in the plane and edges are represented by regions that have an unobstructed line of sight to each other; confluent drawings, in which edges are represented as smooth curves within mathematical train tracks; fabrics, in which nodes are represented as horizontal lines and edges as vertical lines; and visualizations of the adjacency matrix of the graph. |
| | | |
− | 节点链接图可被其他画图方式替代,包括邻接表示法,如圆填充,其中顶点表示为平面上不相交的区域,边表示为区域之间的邻接; 交点表示,其中顶点由非相交的几何对象表示,而边线由其交点表示;可见性表示,其中顶点由平面中的区域表示,边由彼此无障碍视线的区域表示; 汇流图,其中边表示为数学轨迹上的光滑曲线; 织物,其中顶点表示为水平线,边表示为垂直线; 以及图形邻接矩阵的可视化结点。
| + | 节点链接图可被其他画图方式替代,包括邻接表示法,如'''<font color="#ff8000">圆填充 Circle Packings</font>''',其中顶点表示为平面上不相交的区域,边表示为区域之间的邻接; '''<font color="#ff8000">交点表示 Intersection representations</font>''',其中顶点由非相交的几何对象表示,而边线由其交点表示;可见性表示,其中顶点由平面中的区域表示,边由彼此无障碍视线的区域表示; 汇流图,其中边表示为数学轨迹上的光滑曲线; 织物,其中顶点表示为水平线,边表示为垂直线; 以及图形'''<font color="#ff8000">邻接矩阵 Adjiacency Matrix</font>'''的可视化结点。 |
| | | |
| | | |
第70行: |
第70行: |
| | | |
| *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>'''。然而,应用中经常出现非平面图,因此图形绘制算法通常必须考虑边缘交叉。 |
| | | |
| *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. |
− | 一个图形的面积是它的最小边界盒的大小,相对于任意两个顶点之间的最近距离。面积小的画通常比面积大的画更可取,因为它们可以让图画的特征以更大的尺寸显示,因此更清晰。边界框的纵横比也很重要。
| + | 一个图形的面积是它的最小'''<font color="#ff8000">边界盒 Bounding Box</font>'''的大小,相对于任意两个顶点之间的最近距离。面积小的画通常比面积大的画更可取,因为它们可以让图画的特征以更大的尺寸显示,因此更清晰。边界框的纵横比也很重要。 |
| | | |
| *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>''',并找到尽可能多地显示对称的绘图。一些布局方法自动导致对称图形;另外,一些绘图方法从查找输入图形中的对称性开始,并使用它们来构造绘图。 |
| | | |
| *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. |
第85行: |
第85行: |
| | | |
| *[[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> |
− | 角度分辨率是图形绘制中最锐角的度量。如果一个图的顶点高度高,那么它的角分辨率就会很小,但是角分辨率可以由角的函数来限定。
| + | '''<font color="#ff8000">角度分辨率 Angular Resolution</font>'''是图形绘制中最锐角的度量。如果一个图的顶点高度高,那么它的角分辨率就会很小,但是角分辨率可以由角的函数来限定。 |
| | | |
| *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"/> |
− | 图的斜率数是在具有直线段边(允许交叉)的图中所需的明显边缘斜率的最小值。三次图的斜率数最多为4,五次图的斜率数可能是无界的;4度图的斜率数是否有界仍然是开放的。
| + | 图的'''<font color="#ff8000">斜率数 Slope Number</font>'''是在具有直线段边(允许交叉)的图中所需的明显边缘斜率的最小值。'''<font color="#ff8000">三次图 Cubic Graphs</font>'''的斜率数最多为4,五次图的斜率数可能是无界的;4度图的斜率数是否有界仍然是开放的。 |
| | | |
| | | |
第103行: |
第103行: |
| | | |
| *In [[force-based layout]] systems, the graph drawing software modifies an initial vertex placement by continuously moving the vertices according to a system of forces based on physical metaphors related to systems of [[spring (device)|springs]] or [[molecular mechanics]]. Typically, these systems combine attractive forces between adjacent vertices with repulsive forces between all pairs of vertices, in order to seek a layout in which edge lengths are small while vertices are well-separated. These systems may perform [[gradient descent]] based minimization of an [[energy function]], or they may translate the forces directly into velocities or accelerations for the moving vertices.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Section 2.7, "The Force-Directed Approach", pp. 29–30, and Chapter 10, "Force-Directed Methods", pp. 303–326.</ref> | | *In [[force-based layout]] systems, the graph drawing software modifies an initial vertex placement by continuously moving the vertices according to a system of forces based on physical metaphors related to systems of [[spring (device)|springs]] or [[molecular mechanics]]. Typically, these systems combine attractive forces between adjacent vertices with repulsive forces between all pairs of vertices, in order to seek a layout in which edge lengths are small while vertices are well-separated. These systems may perform [[gradient descent]] based minimization of an [[energy function]], or they may translate the forces directly into velocities or accelerations for the moving vertices.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Section 2.7, "The Force-Directed Approach", pp. 29–30, and Chapter 10, "Force-Directed Methods", pp. 303–326.</ref> |
− | 在基于力的布局系统中,图形绘制软件通过根据基于弹簧系统或分子力学的物理隐喻的力系统不断移动顶点来修改初始顶点的位置。通常,这些系统将相邻顶点之间的吸引力与所有对顶点之间的排斥力结合起来,以寻求一种边长较小而顶点分离良好的布局。这些系统可以执行梯度下降最小化的一个能量函数,或者他们可以把力直接转化为节点的速度或加速度
| + | 在'''<font color="#ff8000">'基于力的布局系统 Force-Based Layout</font>''中,图形绘制软件通过根据基于弹簧系统或分子力学的物理隐喻的力系统不断移动顶点来修改初始顶点的位置。通常,这些系统将相邻顶点之间的吸引力与所有对顶点之间的排斥力结合起来,以寻求一种边长较小而顶点分离良好的布局。这些系统可以执行'''<font color="#ff8000">梯度下降 Gradient Descent</font>'''最小化的一个能量函数,或者他们可以把力直接转化为节点的速度或加速度 |
| | | |
| *[[Spectral layout]] methods use as coordinates the [[eigenvector]]s of a [[Matrix (mathematics)|matrix]] such as the [[Discrete Laplace operator|Laplacian]] derived from the [[adjacency matrix]] of the graph.<ref>{{harvtxt|Beckman|1994}}; {{harvtxt|Koren|2005}}.</ref> | | *[[Spectral layout]] methods use as coordinates the [[eigenvector]]s of a [[Matrix (mathematics)|matrix]] such as the [[Discrete Laplace operator|Laplacian]] derived from the [[adjacency matrix]] of the graph.<ref>{{harvtxt|Beckman|1994}}; {{harvtxt|Koren|2005}}.</ref> |
− | 频谱布局方法使用从图的邻接矩阵派生的矩阵(例如Laplacian)的特征向量作为坐标。
| + | '''<font color="#ff8000">频谱布局方法 Spectral Layout</font>'''使用从图的邻接矩阵派生的矩阵(例如Laplacian)的'''<font color="#ff8000">特征向量 Eigenvector</font>'''作为坐标。 |
| | | |
| *Orthogonal layout methods, which allow the edges of the graph to run horizontally or vertically, parallel to the coordinate axes of the layout. These methods were originally designed for [[VLSI]] and [[Printed circuit board|PCB]] layout problems but they have also been adapted for graph drawing. They typically involve a multiphase approach in which an input graph is planarized by replacing crossing points by vertices, a topological embedding of the planarized graph is found, edge orientations are chosen to minimize bends, vertices are placed consistently with these orientations, and finally a layout compaction stage reduces the area of the drawing.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Chapter 5, "Flow and Orthogonal Drawings", pp. 137–170; {{harv|Eiglsperger|Fekete|Klau|2001}}.</ref> | | *Orthogonal layout methods, which allow the edges of the graph to run horizontally or vertically, parallel to the coordinate axes of the layout. These methods were originally designed for [[VLSI]] and [[Printed circuit board|PCB]] layout problems but they have also been adapted for graph drawing. They typically involve a multiphase approach in which an input graph is planarized by replacing crossing points by vertices, a topological embedding of the planarized graph is found, edge orientations are chosen to minimize bends, vertices are placed consistently with these orientations, and finally a layout compaction stage reduces the area of the drawing.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Chapter 5, "Flow and Orthogonal Drawings", pp. 137–170; {{harv|Eiglsperger|Fekete|Klau|2001}}.</ref> |
第115行: |
第115行: |
| | | |
| *[[Layered graph drawing]] methods (often called Sugiyama-style drawing) are best suited for [[directed acyclic graph]]s or graphs that are nearly acyclic, such as the graphs of dependencies between modules or functions in a software system. In these methods, the nodes of the graph are arranged into horizontal layers using methods such as the [[Coffman–Graham algorithm]], in such a way that most edges go downwards from one layer to the next; after this step, the nodes within each layer are arranged in order to minimize crossings.<ref>{{harvtxt|Sugiyama|Tagawa|Toda|1981}}; {{harvtxt|Bastert|Matuszewski|2001}}; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Chapter 9, "Layered Drawings of Digraphs", pp. 265–302.</ref> | | *[[Layered graph drawing]] methods (often called Sugiyama-style drawing) are best suited for [[directed acyclic graph]]s or graphs that are nearly acyclic, such as the graphs of dependencies between modules or functions in a software system. In these methods, the nodes of the graph are arranged into horizontal layers using methods such as the [[Coffman–Graham algorithm]], in such a way that most edges go downwards from one layer to the next; after this step, the nodes within each layer are arranged in order to minimize crossings.<ref>{{harvtxt|Sugiyama|Tagawa|Toda|1981}}; {{harvtxt|Bastert|Matuszewski|2001}}; {{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Chapter 9, "Layered Drawings of Digraphs", pp. 265–302.</ref> |
− | 分层图绘制方法(通常称为杉山式图)最适合于有向无环图或接近无环的图,例如软件系统中模块或函数之间的依赖关系图。在这些方法中,图的节点使用Coffman Graham算法等方法被安排到水平层中,以这样的方式,大多数边从一层向下到下一层;在这一步之后,将每一层内的节点进行排列,以最小化交叉。 | + | '''<font color="#ff8000">分层图绘制方法 Layered Graph Drawing</font>'''(通常称为杉山式图)最适合于'''<font color="#ff8000">有向无环图 Directed Acyclic Graphs</font>'''或接近无环的图,例如软件系统中模块或函数之间的依赖关系图。在这些方法中,图的节点使用Coffman Graham算法等方法被安排到水平层中,以这样的方式,大多数边从一层向下到下一层;在这一步之后,将每一层内的节点进行排列,以最小化交叉。 |
| | | |
| [[File:Goldner-Harary-linear.svg|thumb| | | [[File:Goldner-Harary-linear.svg|thumb| |
第122行: |
第122行: |
| | | |
| *[[Arc diagram]]s, a layout style dating back to the 1960s,<ref>{{harvtxt|Saaty|1964}}.</ref> place vertices on a line; edges may be drawn as semicircles above or below the line, or as smooth curves linked together from multiple semicircles. | | *[[Arc diagram]]s, a layout style dating back to the 1960s,<ref>{{harvtxt|Saaty|1964}}.</ref> place vertices on a line; edges may be drawn as semicircles above or below the line, or as smooth curves linked together from multiple semicircles. |
− | 弧图,一种布局风格可以追溯到20世纪60年代,将顶点放在一条直线上;边缘可以画成在直线上方或下方的半圆,也可以画成由多个半圆连接在一起的光滑曲线。
| + | '''<font color="#ff8000">弧图 Arc Diagram</font>''',一种布局风格可以追溯到20世纪60年代,将顶点放在一条直线上;边缘可以画成在直线上方或下方的半圆,也可以画成由多个半圆连接在一起的光滑曲线。 |
| | | |
| *[[Circular layout]] methods place the vertices of the graph on a circle, choosing carefully the ordering of the vertices around the circle to reduce crossings and place adjacent vertices close to each other. Edges may be drawn either as chords of the circle or as arcs inside or outside of the circle. In some cases, multiple circles may be used.<ref>{{harvtxt|Doğrusöz|Madden|Madden|1997}}.</ref> | | *[[Circular layout]] methods place the vertices of the graph on a circle, choosing carefully the ordering of the vertices around the circle to reduce crossings and place adjacent vertices close to each other. Edges may be drawn either as chords of the circle or as arcs inside or outside of the circle. In some cases, multiple circles may be used.<ref>{{harvtxt|Doğrusöz|Madden|Madden|1997}}.</ref> |
− | 圆形布局方法将图形的顶点放置在一个圆上,仔细选择圆周上顶点的顺序,以减少交叉,并将相邻的顶点放置在彼此接近的位置。边可以画成圆的弦,也可以画成圆内外的弧线。在某些情况下,可以使用多个圆。
| + | '''<font color="#ff8000">圆形布局方法 Circular Layout</font>'''将图形的顶点放置在一个圆上,仔细选择圆周上顶点的顺序,以减少交叉,并将相邻的顶点放置在彼此接近的位置。边可以画成圆的弦,也可以画成圆内外的弧线。在某些情况下,可以使用多个圆。 |
| | | |
| *[[Dominance drawing]] places vertices in such a way that one vertex is upwards, rightwards, or both of another if and only if it is [[reachability|reachable]] from the other vertex. In this way, the layout style makes the reachability relation of the graph visually apparent.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Section 4.7, "Dominance Drawings", pp. 112–127.</ref> | | *[[Dominance drawing]] places vertices in such a way that one vertex is upwards, rightwards, or both of another if and only if it is [[reachability|reachable]] from the other vertex. In this way, the layout style makes the reachability relation of the graph visually apparent.<ref>{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1994}}, Section 4.7, "Dominance Drawings", pp. 112–127.</ref> |
− | 当且仅当一个顶点可以从另一个顶点到达时,优势画顶点的方式是:一个顶点向上,或向右,或两个顶点同时向上。这样,布局风格使得图的可达性关系在视觉上变得明显。 | + | '''<font color="#ff8000">优势图 Dominance Drawing</font>'''当且仅当一个顶点可以从另一个顶点到达时,优势画顶点的方式是:一个顶点向上,或向右,或两个顶点同时向上。这样,布局风格使得图的可达性关系在视觉上变得明显。 |
| | | |
| | | |
第140行: |
第140行: |
| | | |
| * [[Sociogram]]s, drawings of a [[social network]], as often offered by [[social network analysis software]]<ref>{{Harvard citation text|Scott|2000}}; {{Harvard citation text|Brandes|Freeman|Wagner|2014}}.</ref> | | * [[Sociogram]]s, drawings of a [[social network]], as often offered by [[social network analysis software]]<ref>{{Harvard citation text|Scott|2000}}; {{Harvard citation text|Brandes|Freeman|Wagner|2014}}.</ref> |
− | 社会图,社会网络图,通常由社会网络分析软件提供
| + | '''<font color="#ff8000">社会图 Sociogram</font>''',社会网络图,通常由社会网络分析软件提供 |
| | | |
| * [[Hasse diagram]]s, a type of graph drawing specialized to [[partial order]]s<ref>{{Harvard citation text|Di Battista|Eades|Tamassia|Tollis|1994}}, pp. 15–16, and Chapter 6, "Flow and Upward Planarity", pp. 171–214; {{Harvard citation text|Freese|2004}}.</ref> | | * [[Hasse diagram]]s, a type of graph drawing specialized to [[partial order]]s<ref>{{Harvard citation text|Di Battista|Eades|Tamassia|Tollis|1994}}, pp. 15–16, and Chapter 6, "Flow and Upward Planarity", pp. 171–214; {{Harvard citation text|Freese|2004}}.</ref> |
− | 哈塞图,一种专门用于部分顺序的图形绘制
| + | '''<font color="#ff8000">哈塞图 Hasse Diagram</font>''',一种专门用于部分顺序的图形绘制 |
| | | |
| * [[Dessin d'enfant]]s, a type of graph drawing used in [[algebraic geometry]]{{sfnp|Zapponi|2003}} | | * [[Dessin d'enfant]]s, a type of graph drawing used in [[algebraic geometry]]{{sfnp|Zapponi|2003}} |
− | Dessin d'enfants,代数几何中使用的一种图形画法 | + | '''<font color="#ff8000">'Dessin d'enfants</font>'',代数几何中使用的一种图形画法 |
| | | |
| * [[State diagram]]s, graphical representations of [[finite-state machine]]s{{sfnp|Anderson|Head|2006}} | | * [[State diagram]]s, graphical representations of [[finite-state machine]]s{{sfnp|Anderson|Head|2006}} |
− | 状态图,有限状态机的图形表示
| + | '''<font color="#ff8000">状态图 State Diagram</font>''',有限状态机的图形表示 |
| | | |
| * [[Computer network diagram]]s, depictions of the nodes and connections in a [[computer network]]{{sfnp|Di Battista|Rimondini|2014}} | | * [[Computer network diagram]]s, depictions of the nodes and connections in a [[computer network]]{{sfnp|Di Battista|Rimondini|2014}} |
− | 计算机网络图,描述计算机网络中的节点和连接
| + | '''<font color="#ff8000">计算机网络图 Computer Network Diagram</font>''',描述计算机网络中的节点和连接 |
| | | |
| * [[Flowchart]]s and [[DRAKON|drakon-charts]], drawings in which the nodes represent the steps of an [[algorithm]] and the edges represent [[control flow]] between steps. | | * [[Flowchart]]s and [[DRAKON|drakon-charts]], drawings in which the nodes represent the steps of an [[algorithm]] and the edges represent [[control flow]] between steps. |
− | 流程图和drakon图,其中节点表示算法的步骤,边表示步骤之间的控制流的绘图。
| + | '''<font color="#ff8000">流程图 Flowchart</font>'''和'''<font color="#ff8000">drakon图</font>''',其中节点表示算法的步骤,边表示步骤之间的控制流的绘图。 |
| | | |
| * [[Data-flow diagram]]s, drawings in which the nodes represent the components of an [[information system]] and the edges represent the movement of information from one component to another. | | * [[Data-flow diagram]]s, drawings in which the nodes represent the components of an [[information system]] and the edges represent the movement of information from one component to another. |
− | 数据流程图,其中节点表示信息系统的组件,边缘表示信息从一个组件到另一个组件的移动。
| + | '''<font color="#ff8000">数据流程图 Data-Flow Diagram</font>''',其中节点表示信息系统的组件,边缘表示信息从一个组件到另一个组件的移动。 |
| | | |
| * [[Bioinformatics]] including [[phylogenetic tree]]s, [[protein–protein interaction]] networks, and [[metabolic pathway]]s.{{sfnp|Bachmaier|Brandes|Schreiber|2014}} | | * [[Bioinformatics]] including [[phylogenetic tree]]s, [[protein–protein interaction]] networks, and [[metabolic pathway]]s.{{sfnp|Bachmaier|Brandes|Schreiber|2014}} |
第168行: |
第168行: |
| In addition, the placement and routing steps of electronic design automation (EDA) are similar in many ways to graph drawing, as is the problem of greedy embedding in distributed computing, and the graph drawing literature includes several results borrowed from the EDA literature. However, these problems also differ in several important ways: for instance, in EDA, area minimization and signal length are more important than aesthetics, and the routing problem in EDA may have more than two terminals per net while the analogous problem in graph drawing generally only involves pairs of vertices for each edge. | | In addition, the placement and routing steps of electronic design automation (EDA) are similar in many ways to graph drawing, as is the problem of greedy embedding in distributed computing, and the graph drawing literature includes several results borrowed from the EDA literature. However, these problems also differ in several important ways: for instance, in EDA, area minimization and signal length are more important than aesthetics, and the routing problem in EDA may have more than two terminals per net while the analogous problem in graph drawing generally only involves pairs of vertices for each edge. |
| | | |
− | 此外,电子设计自动化(EDA)的布局和布线步骤在很多方面与图形绘制相似,而在分布式计算中贪婪嵌入的问题也是如此,并且图形绘制文献包括从EDA文献中借来的一些结果。然而,这些问题也在几个重要方面有所不同: 例如,在 EDA,面积最小化和信号长度比美观更重要,EDA中的路由问题可能每个网有两个以上的终端,而图绘制中的类似问题通常只涉及每条边的顶点对。
| + | 此外,'''<font color="#ff8000">电子设计自动化(EDA)Electronic Design Automation</font>'''的布局和布线步骤在很多方面与图形绘制相似,而在'''<font color="#ff8000">分布式计算 Distributed Computing</font>'''中'''<font color="#ff8000">贪婪嵌入 Greedy Embedding</font>'''的问题也是如此,并且图形绘制文献包括从EDA文献中借来的一些结果。然而,这些问题也在几个重要方面有所不同: 例如,在 EDA,面积最小化和信号长度比美观更重要,EDA中的路由问题可能每个网有两个以上的终端,而图绘制中的类似问题通常只涉及每条边的顶点对。 |
| | | |
| | | |