A factor graph is a graph where each node is numbered and if x is a factor of y, then x and y are connected. A graph is planar if it can be drawn on paper with no lines crossing.
1) Create a planar factor graph with nodes numbered from 2 through 23.
2a) [easy] Show that no planar factor graph is possible with nodes numbered 2 through 32.
2b) [hard] Show that no planar factor graph is possible with nodes numbered 2 through 24.
3) If the nodes are numbered 1 though n, find the largest planar factor graph and prove that n+1 is impossible.
Tip: A finite graph is planar if and only if it does not contain as a subgraph either the complete graph K5 or the complete bipartite graph K3,3.
1-14 planar graph. I couldn't get everything in a single ascii graph, so I have two parts
14--2--10
| \ | /|
| \|/ |
7---1--5
/ \
11 13
+---6--12--4
| /|\ | / |\
| | | \|/ | |
| | | 2--/ |
| \ \ |\ |
| | \| \---8
|/-3---1 |
9-----/ \---/
These two graphs have only 1 and 2 in common and between them have all the possible edges connecting nodes 1-14. They can be combined by making the bottom one big enough to plop the top one inside the 1-6-2-8 loop of the bottom one.
Part 3 - graph
