Notation next up previous
Next: Force and Energy Controlled Up: Graph Layout for Previous: Introduction


A (directed) graph G=(V, E) consists of a set V of nodes and a set E of ordered pairs of nodes. An element tex2html_wrap_inline2228 is called an edge of the graph. A graph is undirected if for each edge tex2html_wrap_inline2228 also tex2html_wrap_inline2232 holds. The set tex2html_wrap_inline2234 is the set of predecessors of a node tex2html_wrap_inline2236 . The set tex2html_wrap_inline2238 is the set of all successors of a node v. The sizes of these sets are tex2html_wrap_inline2242 and tex2html_wrap_inline2244 .
The degree of a node v is tex2html_wrap_inline2248 .

A sequence tex2html_wrap_inline2250 is a path from tex2html_wrap_inline2252 to tex2html_wrap_inline2254 if there are edges tex2html_wrap_inline2256 for tex2html_wrap_inline2258 . A cycle is a nonempty path from v to v. A graph without cycles is called acyclic. A graph is dense if it contains many edges and sparse if it contains only few edges. It would be superfluously pedantic to define these notions precisely. A graph with tex2html_wrap_inline2264 is always considered sparse, while a graph with tex2html_wrap_inline2266 is always considered dense.


Georg Sander
Thu Aug 1 15:27:34 PDT 1996