Glossary
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
A
Acyclic
An acyclic graph has no path of edges that starts and ends at the same node.
Adjacent, Adjacency
Nodes are called adjacent if they are connected by an edge.
Edges are called adjacent if they share a common node.
Arc
Other name for edge.
B
Bend
A bend is part of the visual representation of an edge. It determines the coordinates where two segments of the edge connect.
The topology of an edge is determined by its port locations and the locations of its bends.
BPMN, Busines Process Model and Notation
A business process management diagram is a diagram that visualizes the business processes in an organization.
A BPMN diagram consists of a set of elements and connections whose visualization is standardized.
The hierarchic structure of a BPMN diagram makes it predestined to be arranged with a hierarchic layout. The pool nodes or swim lanes can be modeled usint table nodes. The BPMN Editor demo shows both the visual features and the automatic arrangement.
Branch
Other name for edge.
C
Centrality
For the elements of a graph the notion of importance of a single node or edge within the graph structure can be expressed using so-called centrality measures. The centrality value directly denotes the graph element’s importance, i.e., the higher the value, the more important the element.
Closeness Centrality
Closeness centrality is defined as the reciprocal of the sum of shortest path distances of a node to all other nodes in the graph. Therefore, a node with high closeness centrality has short distances to all other nodes of a graph.
Degree Centrality
The degree centrality is determined using the degree (the number incoming and outgoing edges) to determine the centrality value for each node.
Graph Centrality
Graph centrality is defined as the reciprocal of the maximum of all shortest path distances from a node to all other nodes in the graph. Nodes with high graph centrality have short distances to all other nodes in the graph.
Node Edge Betweeness Centrality
Betweenness centrality is a measure for how often a node or edge lies on a shortest path between each pair of nodes in the graph.
Weight Centrality
Weight centrality measures the weight associated with incoming, outgoing, or all edges of a node. When no weights are associated with edges, weight centrality becomes the same as degree centrality.
Chain
A chain contains only nodes with degree 2 as well as its start and end nodes.
Components
A component is a part of a graph where all nodes are connected.
Components, Connected
Connected components are groups of nodes where all nodes are are connected by edges.
Components, Biconnected
A biconnected component is a component where all nodes are linked in a way that it remains connected after removal of one node.
Components, Strongly Connected
A connected component is called strongly connected if there is a path between all pairs of nodes.
Connected Components
Connected
A graph is called connected if there exists an undirected path of edges between every pair of nodes. See also Components, Connected.
Cycle
A path that starts and ends at the same node.
D
Decision Tree
A decision tree is a visual representation of hierarchically successive decisions. It is a method for the automatic classification of data to help identify a strategy most likely to reach a certain goal.
Degree
The overall number of incoming and outgoing edges at a node.
Diagram
A diagram is a graphical representation of data.
Directed
An edge is called directed if it has a distinct source node and a distinct target node, i.e., if it has direction. A graph is called directed if all its edges are directed.
E
Edge
An edge is the representative for a relation between two nodes. An edge is usually depicted as a line connecting its end nodes. To indicate the destination of a directed edge an arrowhead is drawn at the target end of the line.
Depending on the type of diagram edges may represent different kinds of relationships. This is often reflected in their visual representation, e.g. by a special dash pattern or by different colors. It is also common to show extra text information, so-called labels to provide more information. In directed graphs the shape and color of the edge’s arrow heads also provides information about the type of relation.
Depending on the diagram type edges my be drawn as straight lines or lines with bends.
Other names are "arc", "branch", "line", "link", or "relation".
Edge Segment
An edge segment is part of the visual representation of an edge. It connects either a port with a bend, or two bends of the edge. Edges which are drawn as straight line have only one segment which connects both ports of the edge.
Edge Routing (Automatic)
A specialized layout algorithm which alters edge paths by placing bends and probably adjusting the positions of the ports of the edges. The node positions will not be altered by this kind of algorithm. It is often used to straighten edges or route edges around obstacles in diagrams where the node positions are fixed.
Entity Relationship Diagram
A diagram that shows relationships between objects or entities within a system.
F
Family Tree
A family tree (also called a pedigree chart) is a diagram representing family relationships.
Traditionally, family trees were often represented in conventional tree structures. Since a (child) node in a tree may have only one parent node, this approach necessitates certain restrictions with regards to how a family tree may represent the mother and father of an individual. I.e., either both parents of an individual share a single node, or the displayed relationships are restricted to matrilineal or patrilineal descent only.
Modern representations for family relationships bypass the restrictions mentioned above by introducing auxiliary nodes for families. I.e., the individual nodes for mother and father are predecessor nodes of a family node while the nodes representing the couple’s children are successor nodes of the said family node. Since parents must be born before their children, the resulting structures are directed, acyclicgraphs.
Flowchart
A flow chart is a diagram that visualizes a process or workflow.
Force-Directed Layout
A layout algorithm that applies repulsive forces between nodes and attractive forces along edges. For the calculated node positions, the repulsive and attractive forces are balanced.
Another name is organic layout.
Forest
A graph whose connected components are trees.
G
Graph
A graph is a mathematical object defined as consisting of two sets, a node set and an edge set.
Graph, acyclic
A graph that contains no directed cycle.
Graph, directed
A graph is called directed if all its edges are directed.
Graph, undirected
A graph is called undirected if none of its edges has a direction.
Grouped Graph
A graph whose nodes can have other nodes as parent. The parent of a node is referred to as a group node. Nodes with a common parent are considered as being in the same group or being grouped.
H
Hierarchical Layout
The hierarchical layout style aims to highlight the main direction or flow within a directed graph. The nodes of a graph are placed in hierarchically arranged layers such that the (majority of) edges of the graph show the same overall orientation, for example, top-to-bottom. Additionally, the ordering of the nodes within each layer is chosen in such a way that the number of edge crossings is small.
I
Incoming Edge
A directed edge is an incoming edge at its target node.
Indegree
The number of incoming edges at a node.
Inner Node
A node in a tree that has more than one connecting edge, but is not the root node. In particular, in a directed tree an inner node has an arbitrary number of outgoing edges and exactly one incoming edge.
L
Label
A label adds information to a graph element by providing a caption.
Layout
Layout defines the position of objects in space. Referring to graphs, layout defines the position of nodes and bends in a two or three dimensional space.
In computing, layout is the process of calculating these positions, often with respect to various constraints. See also layout algorithm.
Layout Algorithm
Algorithms which calculate the positions of nodes and bends (or more general graph elements) in a two or three dimensional space with respect to various constraints. Different layout algorithms will pursue different goals like reducing edge crossings, keeping paths as short or straight as possible. Examples are
- hierarchical layout which emphasizes the flow direction in a directed graph, often combined with aesthetic aspects like symmetry or reducing the number of edge crossings
- force directed layout or organic layout applies repulsive forces between nodes and attractive forces along edges.
Leaf Node
A node in a tree that has exactly one connecting edge. In particular, in a directed tree a leaf node has no outgoing edges and exactly one incoming edge.
Line
Other name for edge.
Link
Other name for edge.
M
Maximum Flow Problem
The maximum flow problem is an optimization problem that involves finding the maximum flow from source to sink nodes through a network of edges, each with a specified maximum capacity.
Mindmap
A mind map is a diagram that visualizes thoughts and ideas about a topic.
Minimum Cost Flow Problem
The minimum-cost flow problem is an optimization problem to find the cheapest possible way of sending a certain amount of flow through a network with capacities and costs.
Minimum Spanning Tree
See Spanning Tree.
N
Network
See Graph.
Node
A node is a graph item which represents an entity.
O
Organization Chart
An organization chart is a diagram that visualizes the relationships and dependencies between employees, positions, and jobs in an organization.
Outdegree
The number of outgoing edges at a node.
Outgoing Edge
A directed edge is an outgoing edge at its source node.
P
Parallel Edges
Multiple edges between the same two nodes are called parallel edges.
Path
A path is defined a sequence of edges which joins a sequence of distinct nodes.
Planar
A graph is called planar, if it can be drawn in the plane such that there are no edge crossings.
Port
A point where an edge connects (or can connect) to a node.
Ports are used to specify for example
- the exact coordinates (absolute or relative to the node) where an edge connects to a node.
- which kind of edges can connect at this node and at this location.
- to add visual representations which provide further information
Predecessor
The source node of a directed edge which ends at another node is called predecessor of that node. In other words, the predecessor of a node is the node at the opposite of an incoming edge to that node.
R
Reachability
A reachability analysis finds the nodes to which a path exists from a given node.
Relation
Other name for edge.
Reverse Edge
An edge is reverse to another edge if the source node of the edge is the same as the target node of the other edge and the target node of the edge is the same as source node of the other edge.
Root Node
A distinguished node in a tree that has more than one connecting edge. In particular, in a directedtree the root node has an arbitrary number of outgoing edges and no incoming edge.
Rooted Tree
A directedtree with designated node.
S
Sankey Diagram
A Sankey diagram is a diagram that visualizes flow information in which the thickness of the edges is proportional to the flow quantity.
Self-loop
An edge where source and target nodes are identical.
For a directed graph, a self-loop adds one to the indegree and one to the outdegree.
For an undirected graph, a self-loop adds two to the degree of its adjacent node.
Sequence Diagram
A sequence diagram is a diagram that visualizes how and in which order different parts of a system interact with each other to perform a specific task.
Shortest Path Problem
The problem of finding the path between two nodes where the sum of the weights (costs) of its edges is minimized.
Sibling
In grouped graphs two nodes are siblings of each other when they have the same parent.
In trees, two nodes are siblings of each other when their incoming edges have the same source node.
Spanning Tree
A spanning tree of an undirectedconnectedgraph is a subset of its edges that induces a tree that connects all nodes of the graph. A minimum spanning tree of a weighted connected graph is a spanning tree whose edges have minimum overall cost among all spanning trees of that graph.
Successor
The target node of a directed edge which starts from another node is called successor of that node. In other words, the successor of a node is the node at the opposite of an outgoing edge to that node.
Source Node
The origination node of a directededge.
Subgraph
A distinguishable part of a graph.
T
Target Node
The destination node of a directededge.
Tree
A special kind of acyclic graph where all possible pairs of nodes have exactly one path between them. Depending on how trees are drawn, one node may be singled out as the root node.
U
UML
An Unified Modeling Language (short UML) diagram visualizes the structures and behavior of a system and shows the communication with its users.
Undirected
An edge is called undirected if it does not have direction, i.e., there is no distinct source node or target node. A graph is called undirected if all its edges are undirected.
V
Vertex
See node.
Y
yEd
yEd is a powerful desktop application that can be used to quickly and effectively generate high-quality diagrams.
yFiles
yFiles are extensive class libraries that enable to add high-quality diagramming functionality to software applications.
yWorks
Tübingen-based company specializing in tools for graph visualization. Notable products are the graph visualization toolkit yFiles for various platforms, as well as the interactive graph editor yEd.