Incidence graph

In mathematics, an incidence graph or Levi graph is a combinatorial structure that encodes the incidences of a block diagram or a projective plane .

The incidence graph of the Fano level: red colored nodes correspond to the points and blue colored nodes to the straight lines of the Fano level shown below.

definition

The Fano level with binary point numbers (red), which are short for homogeneous coordinates.

Is an incidence structure of a set of "dots" and "blocks" (or "line") , then its incidence graph constructed as a bipartite graph with node set , in the two nodes and be accurately connected by an edge if true. ${\ displaystyle (P, B)}$ ${\ displaystyle P}$ ${\ displaystyle B}$ ${\ displaystyle P \ cup B}$ ${\ displaystyle p \ in P}$ ${\ displaystyle b \ in B}$ ${\ displaystyle p \ in b}$

example

The projective plane above the body is the Fano plane with 7 points and 7 lines. Your incidence graph is the Heawood graph . ${\ displaystyle F_ {2}}$

literature

HSM Coxeter: Self-Dual Configurations and Regular Graphs. Bull. Amer. Math. Soc. 56, 413-455, 1950.
C. Godsil, G. Royle: Incidence Graphs. §5.1 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 78-79, 2001.
T. Pisanski, M. Randić: Bridges between Geometry and Graph Theory. in Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed.CA Gorini). Washington, DC: Math. Assoc. Amer., Pp. 174-194, 2000.

Web links

Wolfram MathWorld: Incidence Graph (with a listing of the incidence graphs of important incidence structures)