# Reference for topological graph theory (research / problem-oriented)

I would be interested in recommendations for topological graph theory texts. I think Gross and Yellen has a great chapter on topological graph theory, and I find Mohar and Thomassen's Graphs on surfaces from 2001 a great reference as well.

Could you recommend more current references, ideally with focus on open problems / research?

• Though old, the classic "Topological Graph Theory" by Gross and Tucker is quite useful Jul 20, 2020 at 14:53

Maybe this is another useful reference for you, now I found the link:

Ralucca Gera, Stephen Hedetniemi, Craig Larson, Teresa W. Haynes (editors) (2018): Graph Theory: Favorite Conjectures and Open Problems

It is actually two volumes, and obviously more recent than the other reference I mentioned. It covers graph theory as a whole and does not focus on topological graph theory only. It is a collection of conjectures and open problems. I would judge it to be clearly at graduate and reserach level, but written in a very "inviting" way and starting from examples.

The reason why I think it could be interesting for you: it is full of research ideas and references. I took an hour or so to leaf through it a few weeks ago and was quite fascinated: many short articles, often starting with a few personal remarks and how the author got interested in a particular field, and then moving very fast to conjectures and open questions in that field. Remarkably, the second volume includes a comprehensive list of 70 conjectures, and closes with 600+ references.

• Just to add one comment to this reference, the first volume is actually from 2016. The second volume is from 2018. Jul 22, 2020 at 13:51

My recommendation, try Lando and Zvonkin (2004): Graphs on Surfaces and Their Applications.

I think it is a great book which applies graphs embedded on surfaces to solving problems from other fields of mathematics. The style is very refreshing, vivid, and lively, I would say. The style reminded me of Hatcher's chapter 0 in his Algebraic Topology text, and of Matousek's book "Using the Borsuk-Ulam Theorem".

I would think the target audience of this book is graduate and research level, for some topics the pace is high. Exellent list of references, I think over 300.

Edit: I was just thinking, maybe the following quote from this book gives you a good indication. The authors are talking about a topological graph here:

"It is not merely a topological object, a graph embedded into (or drawn on) a two-dimensional surface. It is also a sequence of permutations (or, if you prefer, it "is encoded by" a sequence of permutations), which provides a relation to group theory. And it is at the same time a way of representing a ramified covering of the sphere by a compact two-dimensional manifold. Considering the sphere as the Riemann complex sphere we obtain, on the covering manifold, the structure of a Riemann surface. And Riemann surfaces rarely walk by themselves. Usually they keep company with Galois theory, with algebraic curves, moduli spaces and many other exciting subjects."

A great and current reference is "Algorithms for embedded graphs" from Éric C. de Verdière, it is a 66 page synthesis of his course notes from 2017 (find here: http://monge.univ-mlv.fr/~colinde/cours/all-algo-embedded-graphs.pdf). Covers topological graph theory plus related algorithms e.g. to minimize edge length of embedded graphs.

See this quote from the link about the contents of these course notes. Note especially chapters 4, 6, and 7 regarding your OP question. Quote:

The first chapter introduces planar graphs from the topological and combinatorial point of view. The second chapter considers the problem of testing whether a graph is planar, and, if so, of drawing it without crossings in the plane. Then we move on with some general graph problems, for which we give efficient algorithms when the input graph is planar. Then, we consider graphs on surfaces (planar graphs being an important special case). In Chapter 4, we introduce surfaces from the topological point of view; in Chapter 5, we present algorithms using the cut locus to build short curves and decompositions of surfaces. In Chapter 6, we introduce two important topological concepts, homotopy and the universal cover. All these techniques are combined in Chapter 7 to provide algorithms to shorten curves up to deformation.

• this is a great reference Aug 1, 2020 at 8:19

I like a lot the book from Beineke & Wilson (editors) "Topics in Topological Graph Theory" from 2009 for that purpose. Take a look at the article "Open Problems" from Archdeacon in this book. It is just like 5 pages or so, but inspired me a lot. I think you could find it very useful.

I can recommend Topics in Chromatic Graph Theory (Encyclopedia of Mathematics and its Applications) with editors Lowell W. Beineke and Robin J. Wilson. It is from 2015, and if you are interested in chromatic topological graph theory topics, there are three relevant chapters for you:
Chapter 1: Colouring graphs on surfaces, chapter 4: Hadwiger's conjecture, chapter 8: Geometric graphs.
My interest is not so much in topological graph theory research (more interested in applications), but I have read these chapters as well, they are very good. It is definitely gradudate level with current research topics.

Here's the reference page from a computational topology course I took a while back.

To complement the answers from last year, now that the question has become active again, I could add these two monographs that approach the topic from different perspectives.
Referring to the "research-oriented" viewpoint requested by the OP: it helps to study a perspective away from the main stream, if you are research oriented; you will have a better chance of finding an unsolved problem that is doable --- published lists of unsolved problems are typically not of that type....

The Foundations of Topological Graph Theory by Bonnington and Little:

This is an attempt to place topological graph theory on a purely combinatorial yet rigorous footing. The sole requirement for understanding the logical development in this book is some elementary knowledge of vector spaces over the field $$\mathbb{Z}_2$$.

Graphs on Surfaces: Dualities, Polynomials, and Knots by Ellis-Monaghan and Moffatt:

We discuss the interdependency between duality, medial graphs and knots; how this interdependency is reflected in algebraic invariants of graphs and knots; and how it can be exploited to solve problems in graph and knot theory.