Types of Networks and Planar Networks

COMP324 Lectures 2023-02-02

This networks page from Barabási will be a useful external resource for the course.

Existing Definitions

A network is a structure formed by a collection of nodes (vertices) connected by links (edges).

Path

A sequence of distinct nodes, such that nay two successive elements are joined by a link.

The length of a finite path is the number of links in it.

Cycle

A finite path $x_1, x_2, \ldots, x_n$ such that $x_1=x_n$.

Distance

The length of the shortest path between two nodes.

Acyclic Networks

Networks without cycles are called acyclic:

• Trees are an example of acyclic networks.

Bipartite Networks

A network is bipartite if its nodes can be subdivided in two groups with no link joining two nodes in the same group.

Planar Networks

A network is planar if it can be drawn in the plane without lines crossing.

A region in a planar network is an area surrounded by links which do not contain smaller regions. For the following graph:

graph LR
1 --- 2
2 --- 3
1 --- 3
2 --- 5
2 --- 4
3 --- 4
3 --- 4
4 --- 5
5 --- 7
5 --- 6
7 --- 6
subgraph region2
5
6
7
end
subgraph not region
4
subgraph region1
1
2
3
end
end

The girth of a network is the length of the smallest cycle in the network.

For the network above, its girth is 3.

Euler Magic Formula

Every connected planar network with $n$ nodes, $m$ links and $r$ regions satisfies:

\[n - m + r = 2\]

You can visualise regions in a planar graph by counting the number of enclosed regions in the network when projected around a sphere:

This means that there is one additional region when counting the enclosed regions on a 2D projection due to the back of the sphere.

Maximal Networks

Assume that $G$ is a connected planar network with $n$ nodes and $m$ links, and all of its regions have at least $g$ sides. Each link belongs to two regions only.

Hence if $F$ is the collection of all regions:

\[\sum_F\left\vert f\right\vert=2m\]

Where:

• $\left\vert f\right\vert$ is the size of $f$.

As we know that the size of $f\geq g$:

\[gr\geq 2m\]

In this we can substitute the Euler formula:

\[\begin{aligned} g(2-n+m)&\leq2m\\ m&\leq\frac g{g-2}(n-2)\\ m&\leq\frac{gn-2n}{g-2} \end{aligned}\]

where:

• $n$ is the number of nodes.
• $m$ if the number of links.

Non-planar Networks

Consider the following two networks:

graph TD
subgraph K5
a --- b
a --- c
b --- c
a --- d
b --- d
c --- d
a --- e
b --- e
c --- e
d --- e
end

subgraph B33
1 --- 4
1 --- 5
1 --- 6
2 --- 4
2 --- 5
2 --- 6
3 --- 4
3 --- 5
3 --- 6
end

Where:

• $B_{3,3}$ is a fully connected bipartite graph with 3 nodes on each side.
• $K_5$ is a fully connected graph with 5 nodes.

To check for $K5$, select any 5 vertices in a graph and see if there are paths between them that match the $K5$ pattern. Paths are required as there may be additional nodes on the arcs.

Kuratowski’s Principle states:

Any network that is non-planar must contain $K_5$ or $K_{3,3}$ or a network obtained from one of these by replacing a link with a simple path.

Therefore we can identify these shapes in networks to avoid having to use Euler’s formula.