# What is a graph where edges are also vertices ?

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)

-
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

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 .

-

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.

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 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