Glossary

This glossary naturally has a strong emphasis on graph structure related terms and concepts. The listed entries are mainly terms used by the yFiles graph visualization library.

A

Acyclic

Attribute of a graph. A graph is called acyclic when there is no path of edges that starts and ends at the same node.

Adjacent

Edges connecting to a node are called adjacent edges. Also, nodes that are direct neighbors of each other are called adjacent.

Arc

Another name for an edge.

See Also Edge.

B

BCC

See Biconnected Component.

Bend

A bend is part of the visual representation of an edge. It determines the coordinates where two segments of the edge connect.

See Also Edge.

Biconnected Component

A component where an arbitrary node can be removed and the remaining nodes are still connected. Informally, biconnected means that there are at least two different paths to reach a node from another one.

See Also Connectivity, Component.

Bipartition

A graph where the node set can be partitioned into two disjoint sets such that there is no edge between nodes from the same set.

C

Complexity

The minimum amount of resources (like time or memory) it needs to solve a problem/execute an algorithm/accomplish a task.

See Also O.

Component

Part of a graph that fulfills certain connectivity criteria. Components are, e.g., connected, strongly connected or biconnected. In a connected component (or component, for short) every node is reachable from every other node.

See Also Biconnected Component, Connectivity.

Connected

Attribute of a graph or a component. A graph is called connected if it consists of exactly one component.

See Also Component.

Connectivity

Defines the reachability of nodes in a graph. A node is said to be reachable from another one, when there is a path of edges between them. The edges in the path are interpreted undirected.

Cycle

A path of edges that starts and ends at the same node.

D

Directed

Attribute of an edge and a graph. 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 edges from the edge set are directed.

Attribute of a tree. A tree is called directed if all its edges are uniformly pointing towards the leaf nodes.

See Also Graph, Edge, Tree.

Directed Tree

See Directed.

E

Edge

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.

See Also Graph.

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.

See Also Bend, Edge, Port.

G

Graph

Mathematical object defined as consisting of two sets, a node set and an edge set.

See Also Node, Edge.

I

Incoming

Attribute of a directed edge. A directed edge is an incoming edge at its target node.

See Also Directed, Edge, Target.

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.

See Also Root Node, Directed, Tree.

L

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.

See Also Directed, Tree.

Link

Another name for an edge.

See Also Edge.

N

Node

Name for the representative of an entity.

See Also Graph.

O

O

Big-Oh notation. A theoretical measure for the execution of an algorithm. Usually denotes the time (or memory) needed relative to the problem size, i.e., some number of items.

The most frequently encountered complexity classes are (where n is the number of items):

  • O(1), constant time. Does not depend on the size of the problem, i.e., an operation with O(1) always takes constant time.
  • O(n), linear time. The execution time grows proportional to the size of the problem, i.e., if the problem size n doubles, then an operation with O(n) will roughly take twice as long.
  • O(n*n), square time. The execution time grows proportional to the square of the size of the problem, i.e., if the problem size n doubles, then an operation with O(n*n) will roughly take four times as long.

Orthogonal

Popular layout and drawing style. Nodes are usually represented by rectangles, edges are made up of alternating vertical and horizontal segments.

Outgoing

Attribute of a directed edge. A directed edge is an outgoing edge at its source node.

See Also Directed, Edge, Source.

P

Parallel Edges

Multiple edges between the same two nodes are called parallel edges.

See Also Edge.

Path

A sequence of edges connecting two nodes.

Planar

Attribute of a graph. A graph is called planar, if it can be drawn in the plane such that there are no edge crossings.

Port

Explicitly expressed coordinates where the visual representation of an edge connects to a node.

R

Reachability

See Connectivity.

Reflexive Edge

Another name for a self-loop.

See Also Self-loop.

Relation

Another name for an edge.

See Also Edge.

Root Node

A distinguished node in a tree that has more than one connecting edge. In particular, in a directed tree the root node has an arbitrary number of outgoing edges and no incoming edge.

See Also Tree.

Rooted Tree

A directed tree with designated root node.

See Also Tree.

S

Self-loop

Directed edge where source and target node are identical.

See Also Directed, Edge.

Subgraph

Distinguishable part of a graph.

See Also Graph.

Source

Name for the origination node of a directed edge.

See Also Directed, Edge.

T

Target

Name for the destination node of a directed edge.

See Also Directed, Edge.

Tree

An acyclic connected graph where the node set can be divided into one root node, and an arbitrary number of inner nodes and leaf nodes. The edges of a tree are usually interpreted undirected.

Traditionally, a tree is depicted with its root at topmost position and its leaf nodes at the bottom (i.e., it is "growing" downwards).

See Also Root Node, Inner Node, Leaf Node, Directed Tree.

U

Undirected

Attribute of an edge and a graph. 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.

See Also Directed, Edge, Graph.

V

Vertex

Another name for a node.

See Also Node.

XYZ

yWorks

Reputable maker of quality software for state-of-the-art automatic layout and visualization of graphs.