46
$\begingroup$

Precisely speaking, what is the difference between the graph terms of ("vertex" vs. "node") and ("edge" vs. "arc")?

I have read that "node" and "arc" should be used when the graph is strictly a tree.

If there is a precise rule or protocol, please cite a reference.

$\endgroup$
1
  • 2
    $\begingroup$ As far as I can tell, there is no difference. Some people use some terms, and some people prefer others. Perhaps some textbooks make a difference (one idea would be to use different words for directed and undirected graphs), but I'm not aware of any, and these distinctions are not standard anyway. $\endgroup$ Apr 5, 2011 at 23:53

5 Answers 5

42
$\begingroup$

The distinction between vertex and node seems to me to be mostly about discipline (e.g. whether you come from combinatorics or computer science) and is irrelevant. The distinction between edge and arc can sometimes be relevant depending on who's using it: combinatorialists sometimes use "edge" to mean "undirected edge" and "arc" to mean "directed edge," although this usage is not universal.

$\endgroup$
1
  • 2
    $\begingroup$ In addition, "arc" is often used in topological situations; e.g., Diestel defines a polygonal arc as a union of finitely many straight line segments homeomorphic to [0,1] when talking about planar graphs. $\endgroup$ Apr 6, 2011 at 0:19
8
$\begingroup$

You can take a look at "Introduction to Graph Theory" of Douglas B. West.

At page 3/Example 1.1.5 of the Second Edition:

The terms "vertex" and "edge" arise from solid geometry. A cube has vertices and edges, and these form the vertex set and edge set of a graph.

At page 55/Remark 1.4.8 of the Second Edition:

We often use the same names for corresponding concepts in the graph and digraph models. Many authors replace "vertex" and "edge" with "node" and "arc" to discuss digraphs, but this obscures the analogies. Some results have the same statements and proofs; it would be wasteful to repeat them just to change terminology (especially in Chapter 4).

Also, a graph G can be modeled using a digraph D in which each edge uv E E(G) is replaced with UV, vu E E(D). In this way, results about digraphs can be applied to graphs. Since the notion of "edge" in digraphs extends the notion of "edge" in graphs, using the same name makes sense.

So according to this book, vertices and edges are for undirected graphs due to the analogy with solid geometry and node and arcs are for directed graphs.

In computer science, "node" and "edge" are used in both cases. I think the only mistake you could make is to use the term "arc" for undirected graph.

$\endgroup$
3
  • $\begingroup$ I am confused, in the penultimate paragraph you say "vertices and edges are for undirected graphs..." and then "node and arcs are for undirected graphs". Both for undirected graphs? $\endgroup$
    – Cragfelt
    Nov 17, 2017 at 6:22
  • $\begingroup$ I think the second undirected could be a typo $\endgroup$
    – dreua
    Nov 20, 2017 at 15:56
  • $\begingroup$ Indeed, I have corrected it thanks :) $\endgroup$ Dec 18, 2017 at 16:03
3
$\begingroup$

My readings suggests "arc" and "edge" are conceptually the same. Yet, LEMON ( http://lemon.cs.elte.hu/trac/lemon )has separate functions/methods for arcs & edges. I have played with it but not enough to understand the difference, in their usage.

$\endgroup$
1
$\begingroup$

As I was wondering the same, I stumbled upon some extra information. I'm reading a book about Computational Geometry.

In this book a graph is drawn within a polygon, to avoid ambiguity they used edges to talk about parts of the shape and arcs to talk about the graph.

The book says the following

$\dots$ let $G$ be a graph associated with a traingulation, whose arcs are the edges of the polygon $\dots$

$\endgroup$
0
$\begingroup$

In my opinion, both terminologies come from the different perception of graphs and networks. Albert-László Barabási writes in his recent text book.

"In the scientific literature the terms network and graph are used interchangeably:

Network science Graph theory
Network Graph
Node Vertex
Link Edge

Yet, there is a subtle distinction between the two terminologies: the {network, node, link} combination often refers to real systems: The WWW is a network of web documents linked by URLs; society is a network of individuals linked by family, friendship or professional ties; the metabolic network is the sum of all chemical reactions that take place in a cell. In contrast, we use the terms {graph, vertex, edge} when we discuss the mathematical representation of these networks: We talk about the web graph, the social graph (a term made popular by Facebook), or the metabolic graph. Yet, this distinction is rarely made, so these two terminologies are often synonyms of each other."

<tl;dr> Same, same, but different.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.