Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

Is there a name for a kind of graph where edges are vertices in the same graph ?

A example would be :

e1(a,b) e2(c,d) e3(e1,e)

share|improve this question
1  
This could pretty much be interpreted as the hypergraph with edges $\{c,d\}$ and $\{a,b,e\}$ if that is what you want. – Listing Oct 10 '12 at 10:21

2 Answers

up vote 0 down vote

Updated Answer

I am not sure if this is exactly what you are looking for, but one way to have the edges as nodes in the same graph is using Bipartite graphs:

http://en.wikipedia.org/wiki/Bipartite_graph

For example,

$$G = (V,E) = (\{ v_1, v_2 \}, \{ (v_1,v_2) \}).$$

Can be represented by,

$$G' = (V',U,E') = (\{ v_1, v_2 \}, \{ (v_1,v_2) \}, \{ (v_1,(v_1,v_2)), (v_2,(v_1,v_2))\}).$$

Where $(v_1,v_2)$ is now a node, and nodes $v_1$,$v_2$ is connected to it.

Previous Wrong Answer

They are sometimes called "dual graphs" (e.g. http://people.hofstra.edu/geotrans/eng/methods/dual_graph.html). And sometimes called "edge dual graphs".

However, I understand that "dual graphs" can also refer to the dual graphs of planar graphs.

share|improve this answer
No, the 'dual graph' is the graph where the roles of edges and vertices are exchanged. – Listing Oct 10 '12 at 10:19
@Listing - Ah, I see. The edges are nodes in the SAME graph. Thanks. Editing my answer... – Legendre Oct 10 '12 at 10:25
1  
Two problems: (i) The connectivity of $G'$ does not reflect the fact that $v_1$ and $v_2$ are connected by an edge in $G$. (ii) If $e = (v_1,(v_1,v_2))$ is an edge in the graph, and edges are also vertices, then I should be able to connect $e$ to $v_2$ by an edge to create a new graph, but this cannot be represented in your encoding. I think it's fair to say that it is not possible to represent the OP's desired structure as a traditional graph of the form $(V, E \subset V^2)$. – Rahul Narain Oct 10 '12 at 11:37
@RahulNarain - $(v_1,v_2)$ is an edge in $G$, not a vertex. The only vertices are $v_1,v_2$. I wrote $G,G'$ in "(vertices,edges)" format. So, $G'$ actually does reflect the connectivity of $G$. But yes, we cannot meet the requirements of the poster. I was suggesting a separate hypergraph/bipartite graph $G'$ that "represents" the connectivity of $G$. Instead of $G'$ representing its own connectivity. – Legendre Oct 11 '12 at 22:55
up vote 1 down vote

Not sure but in RDF you have that. They are called labelled directed graphs in the "RDF Concepts" spec and directed graphs in RDF Semantics.

For example in Turtle - which is just one notation for RDF Graphs - you can write

@prefix foaf: <http://xmlns.com/foaf/0.1/>.
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.

rdf:type a rdf:Property .
<http://bblfish.net/#hjs> rdf:type foaf:Person .

Here the rdf:type name is in subject position in the first statement (a vertice?) and in predicate position (an edge) in the second sentence .

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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