TransWikia.com

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

MathOverflow Asked on November 3, 2021

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?

7 Answers

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.

Answered by Carlo Beenakker on November 3, 2021

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.

Answered by MathScœrss on November 3, 2021

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.

Answered by sean-waves long on November 3, 2021

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.

Answered by LanJiaoXu on November 3, 2021

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.

Answered by Claus on November 3, 2021

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

Answered by Brendan Wilson on November 3, 2021

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."

Answered by Claus on November 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP