How much topology for graph theory?

Question

I am writing a thesis in the context of descriptive complexity in theoretical computer science and therefore need to study a little bit of graph theory. My background is not mathematics but computer science with a strong interest in mathematics (which means I have not heard advanced lectures but feel comfortable learn more). The focus here is the theoretical background of planar graphs. My starting point is the planar graphs chapter in Diestel 2005.

A surface is a compact connected Hausdorf topological space $S$ in which every point has a neighborhood homeomorphic to the Euclidian plane $\mathbb{R}^2$. An arc, a circle and a disc in $S$ are subsets that are homeomorphic in the subspace topology to the real interval $[0,1]$, to the unit circle $S^1 = \{ x \in \mathbb{R}^2 \mid \|x\|=1\}$, and to the unit disc $\{ x \in \mathbb{R} \mid \|x\| \leq 1\}$, respectively.

These definitions are later used to define planar graphs, plane graphs. Other concepts like topological isomorphisms are also used.

I found all the definitions on Wikipedia and I know what they say. Unfortunately I have no intuition what they mean. For example, I guess an arc is a continuous curve which does not intersect with it. My question is not what the definitions mean but rather what is a good starting point to learn about topology from a computer science perspective (with little background knowledge) in the context of graph theory and how much is really needed? Is it possible to take these topology things as black boxes or is it important to understand?

Answer 1

It seems like what you're getting into is topological graph theory, which mainly concerns embedding graphs into surfaces. The study of planar graphs is a special case of this where the graphs are being embedded into the plane. So in topological graph theory, for example, you might also study graphs which could be linklessly embedded on a torus.

I'm not by any means an expert in this subject, but I wager that if you picked up Topology of Surfaces (which is pretty gentle for a topology book), you could get a good enough handle on the topological side of things to return to Diestel and pick up where you left off.

Answer 2

I found Jeff Erickson's Computational Topology notes very useful when I started with similar requirement of learning about topology from a computer science perspective.

Answer 3

If you really have a good idea of what a homeomorphism is, you can understand most of these definitions pretty easily. A homeomorphism is the equivalent of an isomorphism for topological spaces: if two spaces $X$ and $Y$ are homeomorphic, then they essentially "look the same." For example, any closed interval $[a,b]$ is homeomorphic to the unit interval $[0,1]$, and a closed square of any size in $\Bbb R^2$ is homeomorphic to the unit disk. Homeomorphisms remember essential properties of spaces, like "holes" and "dimension," but forget things like whether or not a space has "corners" (in general, the actual "shape" is not remembered by homeomorphism).

So when you think of the last few definitions you give, you can think of arcs, disks, and circles as embeddings of the unit interval, unit disk, and unit circle into other higher dimensional Euclidean spaces, allowing the objects to be stretched and twisted and deformed without ripping or otherwise essentially altering the structure of the original spaces (presumably you'll be working in Euclidean spaces, but if not, the same idea applies).

As for surfaces, you might want some examples in mind. Spheres, ellipsoids, and cubes (without the interior) are all surfaces by this definition. A surface (at least in $\Bbb R^n$ is going to be a closed, bounded (this is equivalent to compact in $\Bbb R^n$) object that is "two dimensional," meaning that if you pick a point and zoom in, it will basically look like $\Bbb R^2$ (aka, every point has a neighborhood homeomorphic to $\Bbb R^2$).

Things can get a bit weirder in non-euclidean spaces, but if you keep the examples in mind and keep track of your definitions, you can't go wrong. Good luck!