Rogue Wave JViews Maps for Defense > Glossaries > Graph layout glossary
INDEX | PREVIOUS  NEXT

Graph layout glossary

Numerics | A | B | C | D | E | F | G | I | L | M | N | O | P | R | S | T | U | V

Numerics

2-connected graph
Also known as a biconnected graph: A connected graph that will remain a connected graph if any one node is removed. (In other words, a graph in which at least two distinct paths exist between every two nodes.) A 2-connected graph has no cut-edge or cut-node.
A 2–connected graph with nodes laid out from left to right in three levels; level 1: nodes 0, 1, 4; level 2: nodes 5, 3; level 3: nodes 2, 6. The graph shows direct link paths: 0–1, 0–2, 1–4, 1–5, 2–5, 2–6, 3–6, 4–3, 4–6, 5–3. Each of these direct links can be read in the reverse direction. Indirect link paths between nodes are, for example: 0–2–1, 0–1–2, 1–5–3–4, 1–2–6–4, 1–2–5, 2–1–5, 2–6–3–5, 2–5–3–6, 3–4–6, 4–6–3, 5–1–4–3. This list is nonexhaustive.
Back to Top

A

acyclic graph
A graph that has no cycles.
annealing
See simulated annealing .
aspect ratio
The ratio between a width and a height. A square has an aspect ratio of 1.
automatic layout
A layout process where the layout algorithm does everything without any user intervention.
Back to Top

B

biconnected graph
See 2-connected graph.
branch
A subpart of a tree that is itself a tree.
bus topology
A type of network topology where a set of nodes is connected to a bus object.
Back to Top

C

child node
A node connected to the current node that is farther way from the root node. In a tree, all links incident to a parent node end at child nodes, except one, which ends at the parent node's parent node.
cluster
A set of nodes that must be placed close together. Circular layout places clusters as rings or stars. See also ring and star.
connected component
A connected graph or subgraph. A connected component of a flat graph G is a maximal connected subgraph of G.
connected graph
A graph where there is a path connecting each pair of nodes. See also disconnected graph.
Connected graph with paths connecting the following node pairs, reading clockwise: 3 – 7, 3 – 4, 4 – 0, 0 – 3, 0 – 1, 1 – 3, 1 – 5, 5 – 6, 1 – 2, 2 – 4, 2 – 3.
connection
Another name for an edge of a graph. See also edge.
constraint
A specification that limits the area where objects can be placed. For example, there can be a constraint that one object must be placed to the left of another object.
cut-edge
An edge is a cut-edge if the graph is no longer connected when the edge is removed from the graph. In the following graph, the link between nodes 3 and 5 is a cut-edge. Note that its end points are cut-nodes.
Graph with seven nodes and nine edges (links), showing a cut-edge between nodes 3 and 5. Reading clockwise, nodes are ordered as 1, 5, 3, 4, 6, 2, 0. Nodes 5 and 3 are at a lower level than nodes 1 and 4, and at a higher level than nodes 6 and 2. This arrangement has the effect of dividing the graph into a quadrilateral on the left, divided into two triangles that share the hypotenuse, and a triangle on the right, both shapes linked by the cut-edge.
cut-node
A node is a cut-node if the graph is no longer connected when the node is removed from the graph. In the following graph, node 5 is a cut-node.
Graph with six nodes and eight edges (links), showing node 5 as a cut-node. Reading clockwise, nodes are ordered as 1, 5, 3, 4, 2, 0. Node 5 is at a lower level than nodes 1 and 3, and at a higher level than nodes 4 and 2. This arrangement has the effect of dividing the graph into a quadrilateral on the left of node 5, divided into two triangles that share the hypotenuse, and a triangle on the right, both shapes share the cut-node 5.
cycle
A path of a graph that begins and ends on the same node. Also called a loop.
cyclic graph
A graph that contains cycles.
cyclomatic number
A number equal to m - n + 1, where m = number of edges and n = number of nodes. In the following illustration, the number of edges = 10, the number of nodes = 8. Therefore, the cyclomatic number is 10 - 8 + 1 = 3.
A hexagonal graph with nodes, reading clockwise: 5, 0, 1, 2, 3, 4. Inside the hexagon, reading from top to bottom, are nodes 6 and 7. Edges run clockwise from nodes 5 to 0, 0 to 1, 1 to 2, to 3, 3 to 4, and 4 to 5. Inside the hexagon, edges run from top to bottom from nodes 4 to 6, 6 to 1, 6 to 7, and 7 to 2.
Back to Top

D

degree
The degree of a node v of a graph G is the number of graph edges which touch v.
directed graph
A graph in which every edge is associated with an ordered pair of nodes. Also called an oriented graph. See also directed link.
directed link
A link with a direction that starts at one of its incident nodes and ends at the other incident node. Directed links are usually drawn with arrowheads that indicate the direction. In a mathematical sense, a directed link is an ordered pair of nodes, while an undirected link is an unordered pair of nodes. See also directed graph.
disconnected graph
A graph containing at least two nodes that are not linked by a path. In the following graph, node 5 is not linked by a path to any other node. Nodes 3 and 4 are not linked by a path to any nodes other than nodes 3 and 4.
Graph containing nodes 5, 3, and 4 that are not linked by paths to the rest of the graph. On the left is part of the graph with three nodes, 0, 1, and 2, linked together by paths in the form of a triangle. In the center is node 5, which is not linked by any path to another node. On the right is node 3 diagonally above node 4 (below and to the left) with a path linking these two nodes.
Back to Top

E

edge
A line connecting two vertices in a graph. An edge is also called a link or a connection. In this documentation, the term link is primarily used for the term edge.
edge crossing
See link crossing.
Back to Top

F

fixed link
A link which remains in the same position during graph layout or link layout. If the user specifies a link as fixed, layout algorithms are not allowed to reshape this link.
fixed node
A node which remains in the same position during graph layout or link layout. If the user specifies a node as fixed, layout algorithms are not allowed to move this node.
flat graph
The converse of a nested graph: a graph of which no node is itself a graph. See nested graph.
Force-directed layout
A class of layout algorithms for creating straight-line drawings of undirected graphs based on an iterative computation of the position of the nodes according to a set of attractive and repulsive forces. These forces are computed in such a way that they tend to produce a layout with only a few link crossings or no link crossings.
Back to Top

G

graph
A finite set of nodes (also called vertices) connected by a finite set of links (also called edges or connections).
graph layout
The process that applies a layout algorithm to a graph. Also the graph drawing that results from the layout process.
graph model
In the context of graph layout, a Java™ class that defines a suitable, generic API for graphs.
grapher
A Java™ object that is used to manage a collection of nodes and links.
grid drawing
A drawing where nodes and link bends have discrete (integer) coordinates.
Back to Top

I

incident
A link-node connection. A link is incident to a node if the node is at one end of the link. A node is incident to a link if that link is incident to the node.
incoming link
A directed link that ends at the node.
incremental layout
A layout process where the result of a previous layout is used as the starting point for applying the layout algorithm a second time to a modified graph in order to minimize the changes.
intercluster link
A link that has its end nodes in different clusters.
intergraph link
In a nested graph, a link whose end nodes are contained in different subgraphs.
intracluster link
A link that has its end nodes in the same cluster.
Back to Top

L

layout algorithm
The process that computes new coordinates for nodes and/or new shapes for links in order to obtain a suitable representation of a graph.
layout region
In the context of graph layout, the rectangle where the graph drawing will be placed when the graph is laid out.
leaf
A node in a tree that is not the root and has at the most one incident edge; that is to say, a node that has no child nodes. The nodes of the tree are named root (one special node), leaves, and inner nodes (all nodes that are not root or leaves).
leaf recursive tree
A nested graph that is a tree and only the leaves of the tree can be subgraphs.
link
Another name for an edge in a graph. In this documentation, the term link is primarily used for edge. See also edge.
link bundle
A set of links (edges) connecting a given pair of nodes in a graph, drawn as a set of parallel lines. See multiple links.
link crossing
Link crossings occur when links intersect at places other than an incident node. Also called edge crossings. Often, layout algorithms are used to minimize the number of link crossings.
Back to Top

M

multiple links
More than one link between the same origin and destination nodes.
Back to Top

N

neighbor nodes
The nodes that are connected to a given node by a link.
nested graph
A graph that contains nodes that are graphs, that is, a graph that contains nested subgraphs.
node
Another name for a vertex of a graph. In this documentation, the term node is primarily used for vertex.
nonplanar graph
A graph that cannot be drawn without any links crossing other links.
Nonplanar graph with five nodes. labelled 0 to 4, arranged in a pentagon. The following link crossings occur, reading from left to right and top to bottom: From node 3 to node 0, crossing links between nodes 4 to 2 and 4 to 1; from node 3 to node 1, crossing links between nodes 4 to 2 and 0 to 2; from node 4 to node 1, crossing links between nodes 3 to 0 and 2 to 0.
NP-complete
A class of computational problems for which no efficient solution algorithm has been found. Many significant computer science problems, including many graph layout problems, belong to this class.
Back to Top

O

orthogonal drawing
A drawing where each link is drawn as a polygonal chain of alternating horizontal and vertical segments.
outgoing link
A directed link that starts at the node.
Back to Top

P

parent node
A node connected to the current node that is closer to the root node. In a tree, all links incident to a parent node end at child nodes, except one that ends at the parent node's parent node.
path
A sequence of consecutive nodes leading from one node to another using the links of the graph. It is the route along the links through the nodes in a graph. The length of a path is the number of links traversed.
planar graph
A graph that can be drawn with no links crossing other links.
Nodes are arranged in the following order running clockwise from 12 o’clock: 1, 2, 3, 4 (in 6 o’clock position), 5, and 0. Node 6 is positioned centrally within the shape formed by the disposition of the other nodes and the links connecting each node. Each node, except nodes 1 and 4, has two links, one connecting it to the preceding node and one to the following node. Nodes 1 and 4, in addition to the links to the preceding and following nodes, have a link to node 6.
polyline drawing
A drawing where each link is drawn as a polygonal chain.
preferred layout
In the context of Recursive Layout, the layout instance set as the one to be used for each graph. It is stored in a property of the graph.
Back to Top

R

radial drawing
A layout style where the nodes are placed radially around a root node.
recursive
The fact that the same mechanism that is applied to a large structure is also applied to its substructures. A recursive layout that is applied to a nested graph is also applied to each subgraph.
ring
A type of network topology where the nodes are arranged in a circular configuration.
A circular graph with nine nodes arranged equidistantly in a ring. Each node has an incoming and an outgoing link, such that the node is linked once to the preceding node in the ring and once to the following node. Thus, this disposition of nodes and links forms a ring network topology.
root
In a tree, the root is only one specified node. In a directed graph, a root is a node that has no incoming links.
Back to Top

S

seed value
The value that is used for the initialization of a random number generator. Some layout algorithms use random numbers during the layout computation.
self-link
A link whose origin and destination nodes are the same node.
semiautomatic layout
A layout process where the user makes manual improvements to the result of the automatic layout process.
sibling node
Child nodes that have the same parent node are called sibling nodes.
simulated annealing
A mathematical technique assisted by a temperature scheme to find a good approximation of the optimum with respect to a certain goal. Simulated annealing was originally inspired by the physical effect of steel annealing when steel is heated and cooled down slowly. In graph layout, simulated annealing is used to place labels in such a way that they do not overlap with one another or with nodes and links.
spanning tree
A minimal subgraph, defined as follows: A spanning tree S of a flat graph G is a subgraph of G containing all the nodes of the graph and whose links are a subset of the links of the graph. The number of links of G that are not present in S must be the minimum number for which there are no cycles in S. The spanning tree is shown by the red links in the following illustration.
A graph consisting of four nodes, 1, 4, 6, and 2, arranged at the four corners of a square with an outer triangle formed on the left side of the square, formed by nodes 2 and 1 and a third node 0. Inside the square, approximately halfway between the upper and lower sides are, reading from left to right, nodes 5 and 3. Node 3 is slightly lower than node 5. Links exist between the following nodes: 0 to 2; 1 to 4, 1 to 5, 1 to 0; 4 to 6; 6 to 3; 2 to 1, 2 to 5, 2 to 6; 3 to 4; 5 to 3. The spanning tree is formed by the following links: 0 to 2, 2 to 6, 2 to 1, 1 to 5, 5 to 3, 3 to 4.
spline
One possible appearance of a link connecting nodes: it is a smooth curve governed by control points.
star
A type of network topology where the nodes are arranged on a circle with each node being connected to a center node.
A graph with 11 nodes arranged in a circle and each of these nodes is connected by a single link to a twelfth central node, like the spokes of a wheel.
straight-line
Denotes a drawing where each link is drawn as a straight line segment.
subgraph
A graph that is contained in another graph. In flat graphs, G' is a subgraph of G if its node and link sets are included in the node and link sets of G.
In nested graphs, a node that is a graph is called a subgraph of the nested graph.
Back to Top

T

tip-over
A placement strategy for trees where child nodes are alternately arranged horizontally or vertically.
topology
The structure of a graph. Two drawn graphs have the same topology if you can obtain one drawing from the other by moving the nodes and reshaping the links.
tree
An undirected tree is a connected undirected acyclic graph (that is, a graph that does not contain any cycles). A directed tree is a connected directed graph where each node has exactly one incoming link except the root node, which has no incoming links.
Root node 0 is positioned towards the center of the tree with outgoing links to node 1 above, node 2 to the left and slightly lower, and node 3 to the right and lower. The nodes other than the root are, reading clockwise, 1, 6, 3, 5, 2, 4. The remaining links connect the following nodes: 2 and 4, above and slightly to the left of node 2; 2 and 5, below and to the right of node 2; 3 and 6, directly above node 3.
Back to Top

U

undirected graph
A graph in which every link is associated with an unordered pair of nodes. See also undirected link.
undirected link
A link that has no specific direction. Contrary to directed links, undirected links have no ordering between both incident nodes. In a mathematical sense, a directed link is an ordered pair of nodes; an undirected link is an unordered pair of nodes. See also directed link and undirected graph.
Back to Top

V

vertex
An element of the graph that can be connected by edges. A vertex is also called a node. In this documentation, the term node is primarily used for the term vertex. A graph consists of a finite set of vertices connected by a finite set of edges (also called links or connections). In drawings, vertices are often displayed as boxes and edges are often displayed as lines.
Back to Top
PREVIOUS  NEXT
© Copyright Rogue Wave 2015. Legal Terms