mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, topological graph theory is a branch of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

. It studies the embedding of graphs in

surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...

s, spatial embeddings of graphs, and graphs as

topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...

s. 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 A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, a sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...

for example, without two edges intersecting. A basic embedding problem often presented as a

mathematical puzzle Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must find a solution that sati ...

is the

three utilities problem The three utilities problem, also known as water, gas and electricity, is a mathematical puzzle that asks for non-crossing connections to be drawn between three houses and three utility companies on a Plane (geometry), plane. When posing it in ...

. Other applications can be found in printing

electronic circuit An electronic circuit is composed of individual electronic components, such as resistors, transistors, capacitors, inductors and diodes, connected by conductive wires or Conductive trace, traces through which electric current can flow. It is a t ...

s where the aim is to print (embed) a circuit (the graph) on a

circuit board A printed circuit board (PCB), also called printed wiring board (PWB), is a laminated sandwich structure of conductive and insulating layers, each with a pattern of traces, planes and other features (similar to wires on a flat surface) ...

(the surface) without two connections crossing each other and resulting in a

short circuit A short circuit (sometimes abbreviated to short or s/c) is an electrical circuit that allows a current to travel along an unintended path with no or very low electrical impedance. This results in an excessive current flowing through the circuit ...

Graphs as topological spaces

To an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

we may associate an

abstract simplicial complex In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely c ...

''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 In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysi ...

,1per 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 In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function ...

, the notion of a connected graph coincides with topological connectedness, and a connected graph is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

its

fundamental group In the mathematics, mathematical field of algebraic topology, the fundamental group of a topological space is the group (mathematics), group of the equivalence classes under homotopy of the Loop (topology), loops contained in the space. It record ...

is trivial. Other simplicial complexes associated with graphs include the

Whitney complex Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques (complete subgraphs) of an undir ...

or ''clique complex'', with a set per

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

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 In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...

). The matching complex of a

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

is called a '' chessboard complex'', as it can be also described as the complex of sets of nonattacking rooks on a chessboard.

Example studies

John Hopcroft and

Robert Tarjan Robert Endre Tarjan (born April 30, 1948) is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees a ...

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 Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such ...

. Fan Chung et al 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 embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) ...

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

Notes

{{reflist

Graphs as topological spaces

Example studies

See also

Notes