Projects Glossary

This glossary contains informal definitions of some of the terms used in the descriptions of the individual projects which may or may not be familiar to all readers.

bounded set

A set that can be placed inside a sufficiently large circle or sphere.

caterpillar

A caterpillar is a tree in which there is some path p in the tree, and every other vertex of the tree is adjacent to some vertex of p.

center

The center of a graph is the subgraph induced by the central vertices of a graph.

central vertex

A central vertex of a graph is one with minimal eccentricity.

circuit

A graph has a circuit if there is some vertex v in the graph for which it is possible to move along distinct edges of the graph and return to v.

complete graph

A graph where each vertex is joined to every other vertex by exactly one edge.

connected graph

A graph in which it is possible to move between any pair of vertices by moving along the edges of the graph.

convex hull

The convex hull of a set of points is the intersection of all convex sets which contain the points.

convex set

A set is convex when the line segment which joins any two points in it lies totally within the set.

degree

(See valence.)

diameter

The diameter of a graph is the largest distance that can occur between any two vertices in the graph.

digraph

A geometric diagram consisting of a finite number of dots called vertices joined by a finite number of curved or straight line segments with an arrow on each called directed edges.

disjoint

Two sets are disjoint if they have no element in common.

distance between vertices in a graph

The distance between two vertices in a graph is the number of edges in a path between the vertices which has the fewest edges.

eccentricity of a vertex

The eccentricity of a vertex v of a graph is the largest distance that any vertex can have from v.

equilateral polygon

A polygon for which all the sides have the same length.

graph

A geometric diagram consisting of a finite number of dots called vertices joined by a finite number of curved or straight line segments called edges.

hamiltonian circuit

A tour of the vertices of a graph which begins and ends at the same vertex of the graph and which visits each vertex of the graph once and only once moving along distinct edges of the graph.

induced subgraph

A subgraph of a graph obtained by selecting some set of vertices of the original graph and adding the edges of the original graph which join vertices in this set.

invalence

In a directed graph, the number of local line segments whose arrow points into a vertex.

isometry

A distance preserving transformation.

k-connected graph

A graph is k-connected if for any two vertices of the graph u and v there are at least k paths from u to v that have only the vertices u and v in common.

k-valent

A graph in which every vertex has valence (degree) k.

net

A plane polygon with diagonals which can be folded up into a polyhedron, sometimes in more than one way.

outerplanar graph

A plane graph all of whose vertices lie on a single face.

outvalence

In a directed graph, the number of local line segments whose arrow points away from a vertex.

planar graph

A graph which is or can be drawn in the plane so that its edges meet only at vertices.

plane graph

A graph which has been drawn in the plane so that edges meet only at vertices.

polyhedron

A 3-dimensional solid with flat surfaces as faces. A polyhedron need not be convex or bounded.

prime

A prime is an integer greater than 1 whose only divisors are 1 and itself.

spanning tree

A spanning tree of a connected graph is a subgraph which is a tree and which contains all the vertices of the graph.

3-polytope

A convex 3-dimensional bounded polyhedron.

tree

A tree is a graph which is connected but contains no circuits.

triangulation of a (plane) polygon

A polygon has been triangulated if diagonals connecting vertices of the polygon have been drawn which lie completely in the polygon, and the resulting graph (except perhaps for the infinite face) has all triangular faces.

valence

In a graph, the number of (local) ends of segments which meet at a vertex. (Another term for the valence of a vertex is its degree.)

Home