# Talk:Accessible pointed graph

WikiProject Computing (Rated Stub-class, Low-importance)
This redirect is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub  This redirect does not require a rating on the project's quality scale.
Low  This redirect has been rated as Low-importance on the project's importance scale.

## Origin of terminlogy?

Did anyone before Aczel (1988) use this terminology? I agree that it's less confusing than the received one, which is actually RDG (rooted directed graph or rooted digraph), particularly as Aczel also defines pointed graph. JMP EAX (talk) 17:58, 23 July 2014 (UTC)

Not to my knowledge. I think the initial version of this article was written and named by someone who knew only about Aczel's work and not about earlier uses of the same concept. (Perhaps it's worth noting that Aczel doesn't seem to be limiting the scope of the definition to *finite* graphs, as some other works in this area probably implicitly do.)

## And

I think the authors who defined rooted graph (instead of rooted digraph) as this were a bit sloppy. The paper of Aggarwal et al. in particular is so, as they they freely mix the terms graph and directed graph throughout the paper, but they usually mean directed graph when they say graph, e.g. "Suppose that we want to perform depth-first search in an n-vertex directed graph G starting from some vertex r. Any such search will visit exactly the vertices reachable from r using directed paths. We call a graph rooted at a vertex if the vertex can reach all other vertices through directed paths. We assume, for the moment, that G is rooted at r and our goal is to build a directed depth-first search spanning tree rooted at r for G." JMP EAX (talk) 18:05, 23 July 2014 (UTC)

You marked as dubious the claim that this paper uses the phrase "rooted graph" to mean the same thing as the subject of the article. Is that claim in any doubt? Or do you merely object to the paper because they use the word "graph" without every time qualifying it by whether it is directed or undirected? That seems a silly reason to object to a source. —David Eppstein (talk) 18:27, 23 July 2014 (UTC)
It seems a low quality source as far as giving definitions is concerned, for the reasons explained above. The much more common term found in CS papers is rooted digraph or rooted directed graph, which isn't even mentioned on this page. You are assuming they really wanted to defined "rooted graph" as a whole term, but I think the only thing clear is that they are defining the meaning of rooted as a qualifier for directed graphs. Eliding "directed" is not without consequence in this case, because rooted graph is usually defined as something else/simpler in the undirected case. If the paper said "Definition: a rooted graph [with this in emphasis] is a [blah, blah...]" I would agree they really intended to define "rooted graph" as phrase term. But that's not clear at all from their writing, which I interpret as I explained above. So, I think it is a bit of WP:OR to assume they define "rooted graph" as a phrase term from their rather unclear writing. JMP EAX (talk) 18:43, 23 July 2014 (UTC)
It is a peer-reviewed paper published in one of the best journals in algorithms research, by three respected algorithms researchers. It is not a low-quality source. If the terms (plural) "rooted digraph" or "rooted directed graph" also appear in the literature, then we should mention them as well; there's no requirement that we be constrained to mentioning only one alternative name. —David Eppstein (talk) 18:52, 23 July 2014 (UTC)
Agreed on the latter, but I really don't think the paper you plaudit defines the term "rooted graph", but only the qualifier "rooted" for directed graphs. Here's the same quote I gave initially with the italics from the original: "Suppose that we want to perform depth-first search in an n-vertex directed graph G starting from some vertex r. Any such search will visit exactly the vertices reachable from r using directed paths. We call a graph rooted at a vertex if the vertex can reach all other vertices through directed paths. We assume, for the moment, that G is rooted at r and our goal is to build a directed depth-first search spanning tree rooted at r for G." There's no "rooted graph" defined there, only the qualifier rooted is emphasized. And your implication that a good journal can't publish a paper with a minor unclear part is rather silly. Anyway, changing in our article "These graphs have also been called rooted graphs." to "These graphs have also been called rooted." would be in line with the source, but it's of course rather elliptic. JMP EAX (talk) 19:05, 23 July 2014 (UTC)

## Merge?

What I'm wondering is why we need three separate articles, this one, rooted graph, and flow graph for what are all the same thing or very close to the same thing. Maybe they should be merged? (I think, if we do merge, that rooted graph should be the primary name — the name here and the flow graph name are both too specific to a particular application.) —David Eppstein (talk) 19:58, 23 July 2014 (UTC)