Incidence (graph)

An incidence graph is a Levi graph.

In graph theory, a vertex is incident with an edge if the vertex is one of the two vertices the edge connects.

An incidence is a pair ${\displaystyle (u,e)}$ where ${\displaystyle u}$ is a vertex and ${\displaystyle e}$ is an edge incident with ${\displaystyle u}$.^[1] Two distinct incidences ${\displaystyle (u,e)}$ and ${\displaystyle (v,f)}$ are adjacent if and only if ${\displaystyle u=v}$, ${\displaystyle e=f}$, or the edge ${\displaystyle uv}$ equals ${\displaystyle e}$ or ${\displaystyle f}$.

A graph can be formally defined as an ordered triple ${\displaystyle (V,E,\psi )}$, where ${\displaystyle V}$ is the set of vertices, ${\displaystyle E}$ is the set of edges, and ${\displaystyle \psi }$ is an incidence function (or incidence mapping) that maps each edge to a pair of vertices.^[2][3] For an edge ${\displaystyle e\in E}$, if ${\displaystyle \psi (e)=(u,v)}$, then ${\displaystyle u}$ and ${\displaystyle v}$ are called the end-vertices (or endpoints) of the edge ${\displaystyle e}$, and the edge ${\displaystyle e}$ is said to be incident with vertices ${\displaystyle u}$ and ${\displaystyle v}$.

A graph can also be specified as an incidence structure ${\displaystyle S=(P,B,I)}$, where ${\displaystyle P}$ is a set of "points" (the vertices), ${\displaystyle B}$ is a set of "blocks" (the edges), and ${\displaystyle I}$ is the incidence relation between them.^[4]

Incidence matrix

Main article: incidence matrix

The incidence matrix of an undirected graph ${\displaystyle G=(V,E)}$ without self-loops is an ${\displaystyle n\times m}$ matrix ${\displaystyle A=a_{ij}}$, where ${\displaystyle n=|V|}$ is the number of vertices and ${\displaystyle m=|E|}$ is the number of edges. The rows correspond to vertices and the columns correspond to edges, with

${\displaystyle a_{ij}=\left\{{\begin{array}{rl}\,1&{\text{if vertex }}v_{i}{\text{ is incident with edge }}e_{j},\\0&{\text{otherwise.}}\end{array}}\right.}$

Each column of the incidence matrix contains exactly two 1s (corresponding to the two endpoints of an edge). Therefore, the sum of all row vectors equals the zero vector modulo 2, making the rows linearly dependent over ${\displaystyle \mathrm {GF} (2)}$ (the field with two elements). This implies that ${\displaystyle \mathrm {rank} (A)\leq n-1}$.^[4] For a connected graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices, an ${\displaystyle (n-1)\times (n-1)}$ submatrix of ${\displaystyle A(G)}$ is non-singular if and only if the ${\displaystyle n-1}$ edges corresponding to its columns form a spanning tree of ${\displaystyle G}$.^[4]

A separate form of incidence matrix exists for directed graphs, where an entry may be ${\displaystyle -1}$ for edges leaving a vertex (or vice versa, depending on the author's preferred convention).

Incidence coloring

Main article: incidence coloring

An incidence coloring of a graph ${\displaystyle G}$ is an assignment of colors to each incidence of ${\displaystyle G}$ such that adjacent incidences receive distinct colors. The incidence coloring number (or incidence chromatic number) ${\displaystyle \chi _{i}(G)}$ is the minimum number of colors needed for an incidence coloring of ${\displaystyle G}$.^[1] It is equivalent to a strong edge coloring of the graph obtained by subdivising each edge of ${\displaystyle G}$ once.

Determining whether a graph has an incidence coloring with a given number of colors is NP-complete. Specifically, Li and Tu showed in 2008 that it is NP-complete to determine whether a semi-cubic graph (a graph where every vertex has degree 1 or 3) is 4-incidence colorable.^[5] This implies that determining the incidence coloring number is NP-hard for general graphs.

Incidence poset

Main article: incidence poset

The incidence poset of a graph ${\displaystyle G=(V,E)}$ is a partially ordered set ${\displaystyle P=(X,P)}$ where ${\displaystyle X=V\cup E}$ and the partial order is defined by the incidence relation: for ${\displaystyle x,y\in X}$, we have ${\displaystyle x<y}$ in ${\displaystyle P}$ if and only if ${\displaystyle x}$ is a vertex and ${\displaystyle y}$ is an edge incident with ${\displaystyle x}$.^[6] The order dimension (or incidence dimension) of a graph ${\displaystyle G}$, denoted ${\displaystyle \mathrm {dim} (G)}$, is the minimum number of total orders on ${\displaystyle V\cup E}$ whose intersection equals the incidence relation. This notion provides a connection between graph structure and the theory of partially ordered sets. A fundamental result due to Schnyder characterizes planar graphs in terms of incidence dimension:

Theorem:^[6] A graph ${\displaystyle G}$ is planar if and only if ${\displaystyle \mathrm {dim} (G)\leq 3}$.

This characterization implies several classical properties of planar graphs. For instance, it provides an alternative proof that every planar graph has arboricity at most 3, and guarantees the existence of a straight-line embedding in the plane where vertex coordinates have a purely combinatorial meaning derived from the total orders in a realizer of the incidence poset.^[6] The dimension of the incidence poset has been studied for various graph classes. For example, Trotter showed in his survey that graphs arising from certain geometric and combinatorial structures often have bounded incidence dimension, connecting this parameter to broader questions in dimension theory and intersection graphs.^[7]