Topological graph theory

In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, and graphs as topological spaces. [J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987]

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-cottage problem. More important 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

An undirected graph can be viewed as a simplicial complex "C" with a single-element set per vertex and a two-element set per edge [ [http://planetmath.org/?op=getobj&from=objects&id=4250 Graph topology] , from PlanetMath.] . 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 [cite journal|author = Shareshian, John; Wachs, Michelle L.|title = Torsion in the matching complex and chessboard complex|year = 2004|id = arxiv|archive = math.CO|id = 0409054] .

Example studies

John Hopcroft and Robert Tarjan [cite journal|author = Hopcroft, John; Tarjan, Robert E.|title = Efficient Planarity Testing|journal = Journal of the ACM|volume = 21|issue = 4|year = 1974|pages = 549–568|doi = 10.1145/321850.321852] 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 [cite journal|author = Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L.|title = Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design|journal = SIAM Journal of Algorithms and Discrete Methods|volume = 8|issue = 1| year = 1987] studied the problem of embedding a graph into a book with the graph's verticies 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.

References

See also

*Crossing number
*Genus
*Planar graph
*Toroidal graph