Topological graph theory
Inmathematics,topological graph theoryis a branch ofgraph theory.It studies theembedding of graphsinsurfaces,spatial embeddings of graphs,andgraphsastopological spaces.[1]It also studiesimmersionsof graphs.
Embedding a graph in a surface means that we want to draw the graph on a surface, aspherefor example, without twoedgesintersecting. A basic embedding problem often presented as amathematical puzzleis thethree utilities problem.Other applications can be found in printingelectronic circuitswhere the aim is to print (embed) a circuit (the graph) on acircuit board(the surface) without two connections crossing each other and resulting in ashort circuit.
Graphs as topological spaces
[edit]To anundirected graphwe may associate anabstract simplicial complexCwith 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 theunit interval[0,1] per edge, with the endpoints of theseintervalsglued together at vertices. In this view, embeddings of graphs into a surface or assubdivisionsof other graphs are both instances of topological embedding,homeomorphism of graphsis just the specialization of topologicalhomeomorphism,the notion of aconnected graphcoincides withtopological connectedness,and a connected graph is atreeif and only ifitsfundamental groupis trivial.
Other simplicial complexes associated with graphs include theWhitney complexorclique complex,with a set percliqueof the graph, and thematching complex,with a set permatchingof the graph (equivalently, the clique complex of the complement of theline graph). The matching complex of acomplete bipartite graphis called achessboard complex,as it can be also described as the complex of sets of nonattacking rooks on a chessboard.[2]
Example studies
[edit]John HopcroftandRobert Tarjan[3]derived a means oftesting the planarityof 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 tograph drawing.
Fan Chunget al[4]studied the problem ofembedding a graph into a bookwith 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 embeddingsare also used toprovestructural results about graphs, viagraph minor theoryand thegraph structure theorem.
See also
[edit]- Crossing number (graph theory)
- Genus
- Planar graph
- Real tree
- Toroidal graph
- Topological combinatorics
- Voltage graph
Notes
[edit]- ^Gross, J.L.;Tucker, T.W.(2012) [1987].Topological Graph Theory.Dover.ISBN978-0-486-41741-7.
- ^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.CiteSeerX10.1.1.499.1516.doi:10.1016/j.aim.2006.10.014.
- ^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.S2CID6279825.
- ^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.