(Redirected from
Incidence graph)
Levi graph or incidence graph is a bipartite graph associated with an incidence structure.
Any geometric incidence structure of points and lines in Euclidean plane such as Desargues configuration gives rise to a (combinatorial) incidence structure.
Example: Desargues Configuration
Desargues configuration is composed of
- 10 points (red dots) and
- 10 lines
- There are 3 points on each line.
- There are 3 lines passing through each point.
The corresponding Levi graph is the generalized Petersen graph G(10,3), also known as the Desargues graph.
Example: Pappus Configuration
Pappus configuration is composed of
- 9 points and
- 9 lines
- There are 3 points on each line.
- There are 3 lines passing through each point.
See also