Graphics Reference
In-Depth Information
Introduction
5.1
his chapter will cover the uses of graphs for making graphs. his overloading of
terms is an unfortunate historical circumstance that conflated graph-of-a-function
usage with graph-of-vertices-and-edges usage. Vertex-edge graphs have long been
understoodasfundamental tothedevelopmentofalgorithms. Ithasbecomeincreas-
ingly evident that vertex-edge graphs are also fundamental to the development of
statistical graphics and visualizations.
One might assume this chapter is about laying out graphs on a plane, in which
vertices are represented by points and edges by line segments. Indeed, this problem
is covered in the chapter. Nevertheless, we take the point of view of the grammar of
graphics (Wilkinson
), in which a graphic has an underlying model. hus, we
assume a graph-theoretic graph is any graph that maps aspects of geometric forms
to vertices and edges of a graph.
We begin with definitions of graph-theoretic terminology. hese definitions are
assumed in later sections, so this section may be skipped and used later as a glossary
by those not interested in details.
Deinitions
5.2
A graph isaset V togetherwitharelation on V.Weusuallyexpressthisbysaying that
agraphG
is a pair of sets, V is a set of vertices (sometimes called nodes),
and E is a set of edges (sometimes called arcs or links). An edge e
=(
V, E
)
(
u,v
)
,withe
E
and u,v
V, is a pair of vertices.
We usually assume the relation on V induced by E is symmetric; we call such
agraphundirected. If the pair of vertices in an edge is ordered, we call G a directed
graph,ordigraph. Wedenote direction bysaying, with respecttoanode,that an edge
is incoming or outgoing.
Agraphisweighted if each of its edges is associated with a real number. We con-
sider an unweighted graph to be equivalent toa weighted graph whoseedges all have
aweightof
.
Agraphiscomplete if there exists an edge for every pair of vertices. If it has n
vertices, then a complete graph has n
(
n
−
)
edges.
A loop is an edge with u
=
v.Asimple graphisagraphwithnoloops.Twoedges
(
u,v
)
and
(
s, t
)
are adjacent if u
=
s or u
=
t or v
=
s or v
=
t. Likewise, a vertex v is
adjacent to an edge
.
A path is a list of successively adjacent, distinct edges. Let
(
u,v
)
or an edge
(
v,u
)
e
,...,e
k
be a se-
quence of edges in a graph. hissequence iscalled apath if there arevertices
v
,...,
v
k
,...,k.
Two vertices u,v of a graph are called connected if there exists a path from vertex
u to vertex v. If every pair of vertices of the graph is connected, the graph is called
connected.
such that e
i
=(
v
i
−
,v
i
)
for i
=
