Topological graph theory

This article is about the study of graph embeddings. For graphs in the plane with crossings, see topological graph.
Animation detailing the embedding of the Pappus graph and associated map in the torus

In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces.[1] It also studies immersions of graphs.

Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three utilities problem. Other applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit.

Graphs as topological spaces

See also: Graph (topology) and Graph homology

To an undirected graph we may associate an abstract simplicial complex C with a single-element set per vertex and a two-element set per edge. The geometric realization |C| of the complex consists of a copy of the unit interval [0,1] per edge, with the endpoints of these intervals glued together at vertices. In this view, embeddings of graphs into a surface or as subdivisions of other graphs are both instances of topological embedding, homeomorphism of graphs is just the specialization of topological homeomorphism, the notion of a connected graph coincides with topological connectedness, and a connected graph is a tree if and only if its fundamental group is trivial.

Other simplicial complexes associated with graphs include the Whitney complex or clique complex, with a set per clique of the graph, and the matching complex, with a set per matching of the graph (equivalently, the clique complex of the complement of the line graph). The matching complex of a complete bipartite graph is called a chessboard complex, as it can be also described as the complex of sets of nonattacking rooks on a chessboard.[2]

Example studies

John Hopcroft and Robert Tarjan[3] derived a means of testing the planarity of a graph in time linear to the number of edges. Their algorithm does this by constructing a graph embedding which they term a "palm tree". Efficient planarity testing is fundamental to graph drawing.

Fan Chung et al[4] studied the problem of embedding a graph into a book with the graph's vertices in a line along the spine of the book. Its edges are drawn on separate pages in such a way that edges residing on the same page do not cross. This problem abstracts layout problems arising in the routing of multilayer printed circuit boards.

Graph embeddings are also used to prove structural results about graphs, via graph minor theory and the graph structure theorem.

See also

Notes

  1. ^ Gross, J.L.; Tucker, T.W. (2012) [1987]. Topological Graph Theory. Dover. ISBN 978-0-486-41741-7.
  2. ^ Shareshian, John; Wachs, Michelle L. (2007) [2004]. "Torsion in the matching complex and chessboard complex". Advances in Mathematics. 212 (2): 525–570. arXiv:math.CO/0409054. CiteSeerX 10.1.1.499.1516. doi:10.1016/j.aim.2006.10.014.
  3. ^ Hopcroft, John; Tarjan, Robert E. (1974). "Efficient planarity testing" (PDF). Journal of the ACM. 21 (4): 549–568. doi:10.1145/321850.321852. hdl:1813/6011. S2CID 6279825.
  4. ^ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. (1987). "Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design" (PDF). SIAM Journal on Algebraic and Discrete Methods. 8 (1): 33–58. doi:10.1137/0608002.