Combinatorial Dual Graph

Let  be the cycle rank of a graph ,  be the cocycle rank, and the relative complement  of a subgraph  of  be defined as that subgraph obtained by deleting the lines of . Then a graph  is a combinatorial dual of  if there is a one-to-one correspondence between their sets of lines such that for any choice  and  of corresponding subsets of lines,

where  is the subgraph of  with the line set .

Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph. Also, a graph is planar iff it has a combinatorial dual (Harary 1994, p. 115).

REFERENCES

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 113-115, 1994.