From a graph G I want to construct a graph (lets call it) G# with the following properties:

  • Each node and each edge of G is a node of G#
  • For each e in G connecting the nodes n1, n2 there exist the edges connecting e,n1 and e,n2
  • no other edges exist in G#

G# is then bipartite with the nodes and edges of G being it's disjoint sets´. It's like creating the line graph of G and stopping after the creation of the "new nodes".

Is there a name for this special kind of graph?


It is called the (first) barycentric subdivision of the graph.

  • $\begingroup$ That's a good observation. Of course, instead of constructing a new graph, it can be obtained from the original by subdividing the edges. $\endgroup$ – M. Vinay Jun 27 '14 at 13:00
  • $\begingroup$ Exactly looking for this. Now the baby has a name I can more efficiently search for existing program modules fulfilling my need $\endgroup$ – Lord_Gestalter Jun 27 '14 at 13:36

This is more like the Total Graph than the Line Graph (because the nodes of $G\#$ consist of both the nodes and the edges of $G$), except that adjacency in $G\#$ is determined only by incidence in $G$, rather than both incidence and adjacency in $G$ (which is the case in Line Graphs).

This is called the Incidence Graph in configurations, though it doesn't seem to be popular in graph theory itself. As you correctly said, it is a bipartite graph.


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.