basic network notations
Table of Contents
- \(n\) - number of nodes in total in a network
- \(m\) - number of edges in total in a network
- \(G\) or \(H\) - name of network
- \(u\) or \(v\) or \(x\) or \(y\) - name of generic node in network
Backlinks
maximal planar network
- fact1
- each link belongs to 2 regions(seperating), therefore define \(\text{region } f \in \text{ set of all regions } F\) \[ \sum_{f \in F}{size(f)} = 2 m \]
- fact2
- define all regions have at least \(g\) sides, then \[ g r \le \sum_{f \in F}{size(f)} = 2 m \]
- fact3
the to subsitute \(r = 2 - n + m\), then \[ g(2-n+m) \le 2m \]
which rearranges to
\[ m \le \frac{g}{g-2}(n-2) \]
which defines the upper bound of the number of links in a planar network, equality holds when all regions are of the same size \(g\).