15: Planar Graphs
- Page ID
- 60148
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
- 15.1: Planar Graphs
- Visually, there is always a risk of confusion when a graph is drawn in such a way that some of its edges cross over each other. Also, in physical realisations of a network, such a configuration can lead to extra costs (think about building an overpass as compared with building an intersection). It is therefore helpful to be able to work out whether or not a particular graph can be drawn in such a way that no edges cross.
- 15.2: Euler’s Formula
- Euler came up with a formula that holds true for any planar embedding of a connected graph. If you try to prove Euler’s formula by induction on the number of vertices, deleting a vertex might disconnect the graph, which would mean the induction hypothesis doesn’t apply to the resulting graph. However, there is a different graph operation that reduces the number of vertices by 1 and keeps the graph connected. This operation is called edge contraction.
- 15.3: Map Colouring
- Suppose we have a map of an island that has been divided into states. Traditionally, map-makers colour the different states so as to ensure that if two states share a border, they are not coloured with the same colour. The question is, without knowing in advance what the map will look like, is there a bound on how many colours will be required to colour it? If so, what is that bound? In other words, what is the largest number of colours that might be required to colour some map?
- 15.4: Summary
- This page contains the summary of the topics covered in Chapter 15.