| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Can anyone tell me whether or not the network represented by this connectivity
table could be drawn in a plane? There are seven nodes and the directed paths
are indicated by the 1's in the From/To table. I have forgotten how to tell
if it can be done. The nodes may be placed in any order and the length of the
paths does not matter. Thanks for any help.
---Phil
To 1 2 3 4 5 6 7
_____________________________
From |
1 | 0 1 0 0 0 0 0
|
2 | 0 0 1 1 1 1 1
|
3 | 0 0 1 1 1 1 1
|
4 | 0 0 1 1 1 1 1
|
5 | 0 0 0 1 0 1 1
|
6 | 0 0 0 0 0 0 0
|
7 | 0 0 0 0 0 0 0
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 239.1 | TURTLE::GILBERT | Fri Mar 15 1985 23:12 | 15 | ||
Telling whether a graph is planar is not, in general, easy to decide. The three nodes 2, 3, and 4 are mutually connected. If these nodes and links are placed in the plane, the plane is divided into two regions (inside and outside of the triangle, if you will). Now 5 is connected to 2, 3, and 4. Without loss of generality, let it be outside the triangle. Now 6 is also connected to 2, 3, and 4; it can't be placed in any of the three regions outside the triangle (we are trying to create a *planar* graph), so it's put inside. Finally, 7 is also connected to 2, 3, and 4; it can't be placed in any of the three regions outside the triangle, nor within any of the three regions inside the triangle. Therefore, it can't be added to the graph, without making it planar. As so the connectivity graph is non-planar. and | |||||
| 239.2 | HARE::STAN | Sat Mar 16 1985 02:21 | 5 | ||
If a graph contains K or K , then it can't be planar. 3,3 5 In this case 2,3,4 each connect to 5,6,7; so that is a copy of K . 3,3 | |||||
| 239.3 | HARE::STAN | Sat Mar 16 1985 09:45 | 1 | ||
... and 5,6,7 each connect to 2,3,4. | |||||