Fact-checked by Grok 2 weeks ago

Topological graph theory

Topological graph theory is a branch of graph theory that examines the embeddings of graphs into topological spaces, particularly surfaces, focusing on properties such as planarity, genus, and crossing numbers that are invariant under homeomorphisms.^[1] It treats graphs as geometric objects, with vertices as points and edges as curves, and analyzes how these embeddings interact with the ambient space's topology, including orientable and non-orientable surfaces like the sphere, torus, and projective plane.^[2] The field originated in the early 20th century through efforts to characterize planar graphs, culminating in key results like Kuratowski's theorem (1930), which states that a graph is planar if and only if it contains no subdivision of K_5 or K_{3,3}, and Wagner's equivalent formulation (1937) in terms of minors.^[3] These criteria form the foundation for understanding non-planar graphs, which require embeddings on higher-genus surfaces, where the genus measures the minimum number of handles (for orientable surfaces) or crosscaps (for non-orientable ones) needed for a crossing-free embedding.^[1] Euler's formula, |V| - |E| + |F| = \chi(S), where \chi(S) is the Euler characteristic of the surface S, provides a fundamental relation among vertices (|V|), edges (|E|), and faces (|F|) in cellular embeddings.^[2] Notable advancements include the Ringel-Youngs theorem (1968), which determines the genus of complete graphs K_n and resolves the map color theorem for arbitrary surfaces by establishing the minimum genus required to embed K_n without crossings.^[1] Voltage graphs and branched coverings offer tools for constructing embeddings and deriving genus formulas, while concepts like graph minors and separators enable the study of minor-closed families beyond planarity.^[3] The discipline intersects with combinatorics, geometry, and computer science, influencing applications in network design and algorithmic graph drawing.^[4]

Foundations

Graphs as topological spaces

In topological graph theory, a graph is formally realized as a 1-dimensional CW-complex, where the vertices correspond to 0-cells forming the 0-skeleton, and the edges are 1-cells, each homeomorphic to the closed interval [0,1], attached along their boundary spheres S^0 (the two endpoints) to the appropriate vertices via continuous attaching maps.^[5] This construction equips the graph with a natural topology, specifically the weak topology induced by the CW-structure, ensuring that the space is Hausdorff and, for finite graphs, compact.^[5] The topological realization of a graph G = (V, E) is obtained by taking the disjoint union of points for each vertex in V and intervals for each edge in E, then quotienting by the equivalence relation that identifies the endpoints of each interval with the corresponding vertices; this yields a compact Hausdorff space that preserves the adjacency relations of the original graph.^[5] Such realizations can be embedded into Euclidean space \mathbb{R}^3 (or higher) in a way that maintains the combinatorial structure, though the specific embedding may vary without altering the intrinsic topology.^[5] Two graphs are topologically equivalent if and only if their CW-complex realizations are homeomorphic as topological spaces; this equivalence is independent of any particular drawing or embedding, relying solely on the continuous bijection between the spaces that respects their cell structures.^[5] This homeomorphism invariance highlights that the topological properties of a graph, such as path-connectedness and the number of ends, are combinatorial invariants captured by the abstract structure.^[5] Abstract graphs are defined combinatorially as sets of vertices and edges with incidence relations, whereas their topological embeddings treat them as continuous objects in a space, allowing the application of tools like homotopy and homology; for higher-dimensional analogs, such as polyhedral complexes, simplicial complexes extend this framework by replacing edges with simplices to model faces and volumes while preserving the 1-skeleton as the graph.^[5] A representative example is the cycle graph C_n for n \geq 3, whose realization is a 1-dimensional CW-complex homeomorphic to the circle S^1, consisting of a single 0-cell and a single 1-cell attached via a degree-1 map on its boundary.^[5]

Surfaces and embeddings

In topological graph theory, surfaces are studied as compact 2-manifolds, which are topological spaces locally homeomorphic to the Euclidean plane. These surfaces are classified up to homeomorphism by their Euler characteristic \chi, a topological invariant computed as \chi = V - E + F for a cell decomposition with V vertices, E edges, and F faces, and by their orientability. Orientable surfaces include the sphere (\chi = 2) and the torus (\chi = 0), while non-orientable examples are the real projective plane (\chi = 1) and the Klein bottle (\chi = 0).^[6] A graph embedding on a surface is a continuous injective map from the topological realization of the graph—formed by identifying edges at vertices—to the surface, such that edges map to non-intersecting arcs except at vertices. This topological embedding ensures the graph is represented without unintended intersections on the surface. A cellular embedding refines this by requiring that the complement of the embedded graph consists of faces, each homeomorphic to an open disk, making the embedding a 2-cell embedding where the surface is decomposed into the graph and its disk-like regions.^[6] Combinatorial embeddings provide an algebraic counterpart, specified by a rotation system: at each vertex, a cyclic ordering of incident edges that dictates the local embedding. Rotation systems correspond to topological embeddings on orientable surfaces.^[7] For 3-connected planar graphs, Whitney's theorem equates combinatorial and topological uniqueness, stating that the embedding in the plane is unique up to reflection.^[8] The crossing number \mathrm{cr}_S(G) of a graph G on a surface S is the minimum number of edge crossings in any drawing of G on S. For the plane (or sphere), \mathrm{cr}(G) = 0 if and only if G is planar, marking the boundary case of embedding without crossings.^[6] Voltage graphs offer a constructive method for generating embeddings, particularly coverings. A voltage graph assigns elements (voltages) from a group to edges of a base graph embedding, deriving a covering graph whose embedding lifts the base structure, enabling systematic construction of symmetric or higher-genus embeddings from simpler ones.^[9]

Planarity

Characterizations of planar graphs

Planar graphs are characterized by the absence of certain forbidden substructures, providing both theoretical and computational criteria for determining planarity. These characterizations, developed in the early 20th century, focus on subgraphs and minors that prevent a graph from being embedded in the plane without edge crossings.^[10]^[11] Kuratowski's theorem states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of the complete graph K_5 or the complete bipartite graph K_{3,3}.^[10] This result was established by Kazimierz Kuratowski in 1930, building on earlier work in topology to identify the minimal obstructions to planarity.^[10] A subdivision of a graph H is a graph obtained from H by replacing one or more edges with paths of arbitrary length greater than or equal to one; equivalently, a subgraph of a graph G is a subdivision of H if it is isomorphic to a subdivision of H, meaning the subgraph is homeomorphic to H in the topological sense where vertices of degree greater than two remain fixed and edges are stretched into paths.^[10] For example, subdividing a single edge in K_5 by inserting a new vertex along that edge yields a graph with six vertices that is still non-planar, as it contains a subdivided K_5 as a subgraph.^[10] An equivalent characterization, known as Wagner's theorem, reformulates the condition in terms of graph minors: a finite graph is planar if and only if it has neither K_5 nor K_{3,3} as a minor.^[11] Klaus Wagner proved this in 1937, showing that the family of planar graphs is minor-closed with these two forbidden minors.^[11] A minor of a graph G is a graph obtained from G by a sequence of edge deletions, vertex deletions, and edge contractions (where contracting an edge merges its endpoints into a single vertex and removes any loops or parallel edges).^[11] Unlike subdivisions, which preserve the topological structure by only elongating edges, minors allow for more aggressive simplifications through contractions, potentially identifying non-planarity in graphs where subdivisions are absent but contracted versions of K_5 or K_{3,3} appear; for instance, the Petersen graph has K_{3,3} as a minor but no subdivided K_{3,3} subgraph.^[11] These dual perspectives highlight that planar graphs form a minor-closed family, a property central to Robertson-Seymour theory, though the specific obstructions for planarity are minimal.^[11] The theoretical characterizations enable efficient algorithms for planarity testing. The Hopcroft-Tarjan algorithm from 1974 determines planarity in linear time by constructing a depth-first search tree and iteratively adding paths while checking for conflicts with the forbidden subgraphs, embedding the graph if no such conflicts arise.^[12] More recently, the Boyer-Myrvold algorithm, introduced in 2004, simplifies this process using an edge-addition scheme on biconnected components, employing a data structure to flip embeddings and isolate Kuratowski subgraphs if present, also achieving O(n) time complexity.^[13] These methods confirm planarity constructively by producing an embedding when applicable, without requiring explicit enumeration of all possible subdivisions or minors.^[12]^[13] Euler's formula provides a fundamental relation among the vertices, edges, and faces in a connected planar embedding of a simple graph. For a connected simple planar graph G with V vertices, E edges, and F faces (including the unbounded outer face), the formula states that

V - E + F = 2.

This equality, known as the Euler characteristic for the plane or sphere, holds for any such embedding and serves as a key topological invariant.^[14] The formula can be derived using mathematical induction on the number of edges, assuming the graph is connected and simple. The base case considers a single vertex, where V=1, E=0, F=1, satisfying the equation. For the inductive step, adding an edge either within a face (splitting it into two) or connecting two components (reducing components while adjusting faces) preserves the relation, as verified by incremental changes to V, E, and F. This proof extends to trees and then to general connected planar graphs by adding edges without crossings.^[14] Important consequences follow from combining Euler's formula with the handshaking lemma for faces, which states that $2E \geq 3F since each face is bounded by at least three edges in a simple embedding. Substituting into the formula yields E \leq 3V - 6 for V \geq 3, providing an upper bound on the number of edges in any simple planar graph. Equality holds precisely for maximal planar graphs, which are triangulations where every face, including the outer one, is a triangle.^[14]^[16] These bounds enable direct proofs of non-planarity for certain graphs. For the complete graph K_5, with V=5 and E=10, the inequality E \leq 3 \cdot 5 - 6 = 9 is violated, so K_5 cannot be planar.^[14] A related result is the five color theorem, which states that the chromatic number of any planar graph is at most 5; this is derived from the edge bound. The four color theorem establishes that four colors suffice for planar graphs.^[14]^[17]

Embeddings on higher surfaces

Graph genus

The genus of a graph G, denoted \gamma(G), is the minimum non-negative integer g such that G admits a 2-cell embedding without crossings on an orientable surface of genus g.^[18] The genus g=0 corresponds to the sphere (or plane), g=1 to the torus, and higher values to surfaces with additional handles. Planar graphs, which embed on the sphere, thus have genus 0. This concept extends planarity by quantifying the "complexity" of a graph in terms of the minimal surface required for embedding.^[19] Lower bounds on \gamma(G) often arise from the Euler characteristic \chi = V - E + F = 2 - 2g for a 2-cell embedding on an orientable surface, combined with inequalities on face degrees. For a simple connected graph G with V vertices and E edges, assuming each face has at least three edges (so $2E \geq 3F), it follows that \gamma(G) \geq \lceil (E - 3(V-2))/6 \rceil.^[20] This bound is tight for triangulations and provides a quick test for non-planarity when exceeded for g=0. Upper bounds on \gamma(G) are typically established constructively by exhibiting embeddings on surfaces of specific genus. Seminal methods include current graphs, where an embedding of a base graph is augmented with group-valued currents on darts to derive lifted embeddings, and voltage graphs, which assign group voltages to arcs of a base embedding to generate covering graphs embeddable on the associated surface.^[21]^[19] These algebraic techniques yield canonical upper bounds and have been pivotal in resolving embedding problems for symmetric graphs. A landmark result is the Ringel-Youngs theorem, which solves the Heawood map-coloring conjecture by determining the exact genus of complete graphs: \gamma(K_n) = \lceil (n-3)(n-4)/12 \rceil for n \geq 3. This formula arises from constructive embeddings using current and voltage methods, confirming that K_7 embeds on the torus (g=1) and providing the minimal surface for larger cliques. For example, \gamma(K_8) = 2, requiring a double torus. Computing \gamma(G) is NP-complete in general, even for cubic graphs.^[22] However, polynomial-time algorithms exist for restricted classes, such as apex graphs or those with bounded treewidth, often relying on dynamic programming over partial embeddings or minor-testing.^[22]

Orientable and non-orientable embeddings

Non-orientable surfaces are constructed in topological graph theory by attaching k crosscaps to a sphere, where a crosscap involves identifying antipodal points on the boundary of a disk, resulting in a surface N_k with Euler characteristic \chi = 2 - k. For example, the real projective plane corresponds to k=1 and \chi=1. The genus bounds derived from Euler's formula for embeddings extend analogously to these surfaces, using \chi = 2 - k to obtain lower bounds on the required complexity.^[23] The demigenus \bar{\gamma}(G) of a graph G is defined as the minimal integer k such that G admits a 2-cell embedding on the non-orientable surface N_k. This parameter parallels the orientable genus \gamma(G) but accounts for the topological differences in non-orientable embeddings, where cycles may be one-sided.^[24] An analogous result to the Ringel-Youngs theorem holds for the non-orientable genus of complete graphs, determined by Ringel: \bar{\gamma}(K_n) = \lceil (n-3)(n-4)/6 \rceil for n \geq 3, n \neq 7, with the exception \bar{\gamma}(K_7) = [3](/page/3) established by Franklin.^[25] Embeddings on non-orientable surfaces often differ from those on orientable ones in terms of minimal complexity. For many graphs, \bar{\gamma}(G) \leq 2\gamma(G), reflecting that non-orientable surfaces can sometimes accommodate embeddings with fewer structural modifications. However, this does not always hold; for instance, the complete graph K_7 has \gamma(K_7)=1, allowing an embedding on the torus, but \bar{\gamma}(K_7)=3, as K_7 does not embed on the projective plane (k=1) or the Klein bottle (k=2).^[26] The distribution and enumeration of non-isomorphic embeddings on a fixed non-orientable surface rely on rotation systems, which specify the cyclic order of edges around vertices. According to the Heffter-Edmonds-Ringel principle, each valid rotation system corresponds to a unique embedding (up to homeomorphism) on the associated surface, enabling the systematic counting of distinct embedding configurations for a given graph.^[27] Specific graphs act as obstructions that distinguish embedding possibilities between surfaces. Notably, K_{3,3} fails to embed on the plane (where \gamma=0) due to its non-planarity, yet it admits an embedding on the projective plane (k=1), demonstrating how non-orientable surfaces can resolve certain crossing issues inherent in planar embeddings.^[28]

Advanced concepts

Graph minors and obstructions

The concept of graph minors is fundamental to understanding obstructions for embeddings on surfaces in topological graph theory. A graph H is a minor of G if a graph isomorphic to H can be obtained from G by a sequence of edge deletions, vertex deletions, and edge contractions. Embeddability on a fixed surface is preserved under these operations, so the class of graphs embeddable on any given surface Σ is minor-closed. Thus, membership in this class can be characterized by avoiding a finite set of forbidden minors—graphs that do not embed on Σ but are minimal with this property. This approach generalizes the classical result for the plane, where the forbidden minors are K_5 and K_{3,3}. The Robertson–Seymour theorem establishes that every minor-closed family of finite graphs admits a finite forbidden minor characterization. Proved across a landmark series of 23 papers spanning 1983 to 2004, the theorem demonstrates that the minor relation well-quasi-orders the set of finite graphs, implying finiteness of obstructions for any such family. Historically, Klaus Wagner's 1937 characterization of planar graphs via minors laid foundational groundwork, but it was Robertson and Seymour's work in the 1980s and 1990s that extended this to arbitrary minor-closed properties, including embeddability on higher-genus surfaces. Their proof, exceeding 500 pages, relies on inductive decompositions and has profound implications for algorithmic graph theory, though the full characterization for most surfaces remains computationally intensive.^[29] For embeddings on specific surfaces, the forbidden minors vary in complexity. For the projective plane (non-orientable genus 1), the complete set consists of 35 graphs, explicitly enumerated by Robertson, Seymour, and Thomas. Examples include the complete graph K_8, certain apex graphs over non-planar minors, and intricate triangulations that force higher genus. In contrast, for the torus (orientable genus 1), the full list remains unknown despite extensive computation; Chambers identified 16,629 distinct forbidden minors up to order 11 in 2002, with later efforts suggesting thousands more overall. Key examples among these include K_8 (whose Euler genus is 2) and multipartite graphs like K_{3,3,1,1}, which cannot be embedded without crossings on the torus. These obstructions grow exponentially with genus.^[30] Applications of minor obstructions extend to bounding graph genus and structural decompositions. If a graph G contains no minor forbidden for the surface Σ_k of Euler genus k (roughly orientable genus k/2), then G embeds on a surface of Euler genus at most k-1, implying γ(G) ≤ (k-1)/2 for orientable genus. This provides a practical method to upper-bound genus by testing for a finite (albeit large) set of minors, often via algorithms exploiting the structure theorem. The theory also intersects with treewidth: excluding a fixed minor bounds treewidth by a function of the excluded graph's size, and for surface-embedded graphs, treewidth is O(√g) where g is the genus, linking minor hierarchies—chains of successive minors—to decomposition depths in Robertson–Seymour's framework. These relations enable efficient approximations for genus testing and embedding problems on higher surfaces.^[30]

Map colorings and symmetries

In topological graph theory, map coloring concerns the proper vertex coloring of the dual graph of an embedding, ensuring that adjacent faces receive different colors. The four-color theorem states that every planar map is 4-colorable, meaning no more than four colors suffice to color the countries of any map on the plane or sphere such that no two adjacent countries share the same color. This result, conjectured in the 19th century, was proved in 1976 using a computer-assisted approach that reduced the problem to checking a finite set of unavoidable configurations.^[31] For embeddings on higher-genus surfaces, Heawood's formula provides an upper bound on the chromatic number: for an orientable surface of genus g \geq 1, the chromatic number \chi satisfies

\chi \leq \left\lfloor \frac{7 + \sqrt{1 + 48g}}{2} \right\rfloor.

This bound is tight, as the complete graph K_7 embeds on the torus (g=1) and requires seven colors, achieving equality in the formula. The full Heawood conjecture, stating that this bound is necessary and sufficient except for the plane and Klein bottle, was proved by Ringel and Youngs in 1968 through exhaustive constructions of embeddings for complete graphs on various surfaces.^[32] List coloring extends classical coloring by assigning to each vertex a list of available colors, with the graph being k-choosable if it is colorable from any such lists of size at least k. For planar maps, every such embedding is 5-choosable, a result proved by Thomassen in 1994 using an inductive argument on triangulations with precolored outer cycles. This choosability bound matches the classical coloring number for planar graphs but highlights stronger robustness in list assignments for embedded structures. Symmetries of embeddings are captured by the automorphism group, which preserves the embedding's combinatorial structure. A regular map is an embedding where this group acts transitively on the flags (triples of incident vertex, edge, and face), ensuring maximal symmetry. Such maps on orientable surfaces of genus g \geq 2 have automorphism groups of order at most $84(g-1), as bounded by Hurwitz's theorem on the maximal order of automorphism groups of Riemann surfaces. Self-dual maps are embeddings isomorphic to their duals, preserving the combinatorial type under face-vertex interchange. These arise in symmetric contexts, such as on the sphere, where the 24 possible symmetry pairings classify self-dual configurations via permutation representations. Voltage constructions generate symmetric embeddings by assigning group elements (voltages) to edges of a base graph, lifting to a covering graph whose derived embedding inherits regular or highly symmetric properties; this method, developed by Gross and Tucker, facilitates the creation of orientable and non-orientable regular maps.^[33]^[9]

Examples and developments

Classical studies

One of the earliest and most intuitive examples of a non-planar graph is the complete bipartite graph K_{3,3}, often called the utility graph. This graph arises from the well-known "three houses and three utilities" puzzle, in which three houses must each be connected to three utilities (such as water, gas, and electricity) via pipelines that do not cross. Despite attempts to draw these nine edges without intersections in the plane, at least one crossing is unavoidable, establishing K_{3,3} as non-planar.^[34] The non-planarity of K_{3,3} can be formally verified using a bound derived from Euler's formula for planar graphs. For a simple connected bipartite planar graph (which has no 3-cycles), the number of edges m satisfies m \leq 2n - 4, where n is the number of vertices. For n = 6, this implies m \leq 8, but K_{3,3} has 9 edges, yielding a contradiction.^[35] The Petersen graph provides another foundational non-planar example, notable for its high degree of symmetry as a 3-regular, vertex-transitive graph with 10 vertices and 15 edges. It cannot be embedded in the plane without crossings but has genus 1, allowing a crossing-free embedding on the torus; this embedding highlights its role as a minimal non-planar graph that avoids K_5 as a minor but contains a subdivision of K_{3,3}, per Kuratowski's characterization. Its symmetric properties, including girth 5 and diameter 2, make it a frequent counterexample in graph theory studies.^[36]^[37] Complete graphs K_n offer a systematic series of examples for planarity and higher-genus embeddings. Specifically, K_n is planar for n \leq 4, as K_4 can be drawn without crossings, but K_5 is non-planar, requiring at least one crossing in any plane drawing. For larger n, the minimal genus \gamma(K_n) follows the formula \gamma(K_n) = \left\lceil \frac{(n-3)(n-4)}{12} \right\rceil, which quantifies the orientable surface needed for an embedding without crossings and was derived through solutions to the map-coloring problem on surfaces.^[38]^[39] The Heawood graph exemplifies toroidal embeddings as the point-line incidence structure (Levi graph) of the Fano plane, the finite projective plane of order 2, with 14 vertices (7 points and 7 lines) and 21 edges. This 3-regular graph is non-planar but embeds without crossings on the torus, forming the dual of the complete graph K_7 in its toroidal embedding. Its cage properties as the smallest (3,6)-graph underscore its importance in extremal graph theory.^[40]^[41] Historical examples from the late 19th century further illustrate topological graph theory's roots in map coloring. In 1878, P. G. Tait proposed edge colorings of 3-regular (cubic) planar maps as equivalent to the four-color problem via dual graphs, aiming to show that such graphs are 3-edge-colorable if the faces require at most four colors. This approach influenced Alfred Kempe's 1879 attempted proof of the four-color theorem using chain arguments on Kempe components, which initially seemed successful but was refuted in 1890 due to interlocking chains that prevent simultaneous recoloring.^[42]

Recent advances

Significant progress in characterizing graphs embeddable on surfaces has been made through the extension of Robertson-Seymour theory to surface embeddings, where finite lists of forbidden minors fully describe the minor-closed families for fixed genus. In particular, for the torus (genus 1), Robertson, Seymour, and Thomas established in 1994 that graphs embeddable on the torus exclude a finite set of minors, and explicit complete lists were compiled by the early 2000s, including four forbidden minors for certain subclasses without K_{3,3}.^[43]^[44] These results enabled algorithmic tests for embeddability on low-genus surfaces with polynomial-time complexity for fixed genus.^[29] Probabilistic methods have advanced the study of average genus and random embeddings since the 1990s, providing insights into embedding distributions for typical graphs. Archdeacon initiated computations on average genus in 1988, but key developments came with Archdeacon and Grable's 1995 proof that the genus of the Erdős–Rényi random graph G_{n,p} is asymptotically pn^2/12 with high probability when p \geq (3\ln n)^2 n^{-1/2}.^[45]^[46] Subsequent work in the 2000s and 2010s extended this to bipartite random graphs and refined bounds using probabilistic embedding techniques, revealing that random graphs concentrate around their expected genus.^[47] Book embeddings and related parameters like thickness and queue number have seen algorithmic improvements post-2000, linking topological constraints to layout problems. The book thickness, measuring the minimum pages for a non-crossing linear vertex ordering, was shown to be at most 4 for planar graphs in the 1980s, but recent results established constant thickness (at most 11) for 1-planar graphs in 2016, with implications for queue layouts. Queue number, a variant bounding edge queues in linear orderings, was bounded by O(\log^2 n) for planar graphs in 2017, improving prior \sqrt{n} bounds and connecting to thickness via stack layouts.^[48] These advances facilitate efficient drawings with minimal crossings in multiple layers. Applications of topological graph theory to VLSI design and network topology have grown since 2000, particularly in chip layout and routing optimization. Embedding algorithms ensure non-crossing wire placements in multi-layer circuits, where graph thickness models layer counts to minimize vias and congestion; post-2000 tools incorporate genus bounds for hierarchical layouts in integrated circuits.^[49] In network topology, minor obstructions help design fault-tolerant topologies embeddable on surfaces, aiding scalable routing in data centers.^[50] Despite these advances, key unsolved problems persist as of 2025, including the cycle double cover conjecture, which posits that every bridgeless graph admits an embedding where every edge lies on exactly two cycles, remaining open with recent work focusing on approximations.^[51] Similarly, tight bounds on average genus for general graph classes elude resolution, with incremental lower bounds like \gamma_{av}(G) \geq (4e(G) - 6v_2(G))/ (12n) from 2023, but no major closures on asymptotic behaviors or distributions.^[52]

References

[1]
Topological Graph Theory - Jonathan L. Gross, Thomas W. Tucker
Authors, Jonathan L. Gross, Thomas W. Tucker ; Edition, illustrated, reprint ; Publisher, Courier Corporation, 2001 ; ISBN, 0486417417, 9780486417417 ; Length, 361 ...
[2]
[PDF] Topological Graph Theory
Topological graph theory deals with ways to represent the geometric real- ization of graphs. Typically, this involves starting with a graph and depicting it on ...Missing: definition | Show results with:definition
[3]
[PDF] Topological Graph Theory
Topological Graph Theory. Bojan Mohar. Simon Fraser University. Intensive Research Program in Discrete, Combinatorial and Computational Geometry. Advanced ...
[4]
(PDF) Topological Graph Theory from Japan - ResearchGate
Aug 7, 2025 · This is a survey of studies on topological graph theory developed by Japanese people in the recent two decades and presents a big bibliography.
[5]
[PDF] Algebraic Topology - Cornell Mathematics
This book was written to be a readable introduction to algebraic topology with rather broad coverage of the subject. The viewpoint is quite classical in ...
[6]
[PDF] 23 computational topology of graphs on surfaces
Sep 5, 2017 · Graph embedding (topological definition): A graph G naturally leads to a topological space ˆG, defined as follows: One considers a disjoint set ...
[7]
A Whitney Type Theorem for Surfaces: Characterising Graphs with ...
Jul 23, 2024 · In this paper we have the goal to find systematic and algorithmically feasible methods for the general embedding problem, as follows. In 1932 ...
[8]
Voltage graphs - ScienceDirect.com
A possible way to obtain a complicated graph imbedding in a surface is to derive it as a covering of a simpler imbedding by assigning “voltages” to the edges.
[9]
Sur le problème des courbes gauches en Topologie - EuDML
Sur le problème des courbes gauches en Topologie. Casimir Kuratowski · Fundamenta Mathematicae (1930). Volume: 15, Issue: 1, page 271-283; ISSN: 0016-2736 ...
[10]
Über eine Eigenschaft der ebenen Komplexe
Wagner, K. Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570–590 (1937). https://doi.org/10.1007/BF01594196
[11]
Efficient Planarity Testing | Journal of the ACM - ACM Digital Library
This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an ...Missing: original | Show results with:original
[12]
On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
Jan 1, 2004 · We present new O(n)-time methods for planar embedding and Kuratowski subgraph isolation that were inspired by the Booth-Lueker PQ-tree ...
[13]
[PDF] Planar Graphs
When we draw a graph on a piece of paper, we naturally try to do this as transparently as possible. One obvious way to limit the mess created.
[14]
[PDF] Planar Graphs - Jeff Erickson
Sep 5, 2017 · Euler's formula has several straightforward but useful consequences, whose proofs. 25 we leave as exercises for the reader. A simple planar ...<|control11|><|separator|>
[15]
http://jeffe.cs.%5Billinois
[16]
http://jeffe.cs.illinois.edu/teaching/comptop/2017/chapters/02-planar-graphs.pdf
[17]
Graph Embedding - Kent
Graph embedding involves placing graphs on surfaces, with genus being the number of handles/holes. Planar graphs have genus 0, and nonplanar graphs have genus ...
[18]
https://doi.org/10.3390/sym15020322
[19]
https://doi.org/10.1016/0012-365X(74)90078-1
[20]
[PDF] An Euler-genus approach to the calculation of the crosscap-number ...
As usual in topological graph theory, we denote the closed orientable surface of genus g by Sg and the closed non-orientable surface of crosscap number k by Nk.Missing: demigenus | Show results with:demigenus
[21]
[PDF] Matroids Determine the Embeddability of Graphs in Surfaces ...
... demigenus, crosscap ... Topological graph theory, Wiley-Interscience, New York, 1987. 9. B. Richter, On the non-orientable genus of a 2-connected graph, J.Missing: crosscaps | Show results with:crosscaps
[22]
[PDF] Embedding graphs in surfaces: MacLane's theorem for higher genus
(Indeed, large projective- planar grids have unbounded orientable genus [3], while K7 can be embedded in the torus but not in the Klein bottle [7].)
[23]
[PDF] arXiv:2102.04133v4 [math.CO] 18 Jan 2022
Jan 18, 2022 · By the Heffter-Edmonds-Ringel rotation principle, (σ, α) defines a unique cellular embedding of G on an orientable surface Σ (up to oriented ...
[24]
[PDF] An Algebraic Characterization of Projective-Planar Graphs
Sep 18, 2002 · If |K| is a nonorientable surface, then the demigenus is the crosscap number of the surface. Proposition 4. If S is a surface of demigenus d, ...
[25]
[PDF] Graph Minors
(Robertson & Seymour 2003). For every n > 5 there exists a k 2 N such that every graph not contain- ing Kn as a minor has a tree-decomposition whose torsos are ...
[26]
[PDF] 12 Graph Minors - Jeff Erickson
As part of the proof of the Graph Minor Theorem, Robertson and Seymour proved that in a sense, grids are the only example of a graph with large treewidth. Lemma ...
[27]
Every planar map is four colorable - Project Euclid
Every planar map is four colorable. K. Appel, W. Haken. DOWNLOAD PDF + SAVE TO MY LIBRARY. Bull. Amer. Math. Soc. 82(5): 711-712 (September 1976).
[28]
SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM<xref ...
the complete graph conjecture. We shall prove that if (7) is true, then the Heawood map-coloring conjecture is settled in the affirmative.
[29]
The 24 symmetry pairings of self-dual maps on the sphere
Given a self-dual map on the sphere, the collection of its self-dual permutations generates a transformation group in which the map automorphism group ...
[30]
Utility Graph -- from Wolfram MathWorld
The utility problem posits three houses and three utility companies--say, gas, electricity, and water--and asks if each utility can be connected to each ...<|separator|>
[31]
[PDF] an elementary proof that the utilities puzzle is impossible - Lomont.org
It is equivalent to the graph K3,3 being nonplanar. Here I present a simple proof that can convince even most non- math majors. 1. The Utilities Puzzle.
[32]
Petersen Graph -- from Wolfram MathWorld
pi(z)=(z-2)(z-1)z. The Petersen graph is a cubic symmetric graph and is nonplanar. ... The following table summarizes some properties of the Petersen graph.Missing: genus | Show results with:genus
[33]
[PDF] Embeddings of Small Graphs on the Torus - Computer Science
The dual of K7 on the torus is the Heawood graph, which is the incidence graph of the Fano plane, the 7-point finite projective plane. The dual of a 6 ...
[34]
Graph Genus -- from Wolfram MathWorld
The genus of a disconnected graph is the sum of the genera of its connected components (Battle et al. 1962, White 2001, p. 55), and the genus of a connected ...
[35]
Kuratowski's theorem - Thomassen - 1981 - Journal of Graph Theory
We present three short proofs of Kuratowski's theorem on planarity of graphs and discuss applications, extensions, and some related problems.
[36]
Heawood Graph -- from Wolfram MathWorld
The Heawood graph corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line Levi graph on the Fano plane ( ...
[37]
The Many Names of (7, 3, 1) - jstor
This toroidal embedding is what gives the graph its common name: the Heawood graph. For, in 1890, Percy J. Heawood proved that every graph that can be drawn on.
[38]
Four-Color Theorem -- from Wolfram MathWorld
Fallacious proofs were given independently by Kempe (1879) and Tait (1880). ... "How False Is Kempe's Proof of the Four-Color Theorem?" Congr. Numer. 164 ...
[39]
[PDF] Graph minors and graphs on surfaces12
Graph minors and the theory of graphs embedded in surfaces are fundamentally interconnected. Robertson and Seymour used graph mi- nors to prove a generalization ...
[40]
Forbidden minors and subdivisions for toroidal graphs with no K 3,3 's
For these graphs, we provide the complete lists of four forbidden minors and eleven forbidden subdivisions.
[41]
On the average genus of the random graph - Wiley Online Library
Archdeacon, Calculations on the average genus and genus distribution of graphs. Congres. Number. 67 (1988) 114–124. Google Scholar. 2 D. Archdeacon, The ...
[42]
[PDF] arXiv:1712.09989v3 [math.CO] 7 Apr 2020
Apr 7, 2020 · Abstract. Archdeacon and Grable (1995) proved that the genus of the random graph G ∈ Gn,p is almost surely close to pn2/12 if p = p(n) ≥.
[43]
The Genus of a Random Bipartite Graph
Aug 29, 2019 · Archdeacon and Grable (1995) proved that the genus of the random graph G\in {\mathcal{G}}_{n,p} is almost surely close to pn^{2}/12 if p=p(n)\ ...
[44]
On the Queue Number of Planar Graphs - ResearchGate
Aug 18, 2025 · We prove that planar graphs have O ( log ⁡ 2 n ) O(\log^2 n) queue number, thus improving upon the previous O ( n ) O(\sqrt n) upper bound.
[45]
[PDF] Graph Algorithms for VLSI Power and Clock Networks
... design tasks. Graph theory plays an important role in electronic design automation. (EDA) by providing powerful and versatile algorithms to tackle a variety ...
[46]
(PDF) Graph Theory and Network Topologies - ResearchGate
Apr 12, 2025 · This paper examines the intersection of graph theory and network topologies, highlighting their significance in real-world applications.
[47]
https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/genus-of-a-random-bipartite-graph/AB463CE386957B88BE99FD1C9D2C42D5
[48]
New bounds for the average genus and average number of faces of ...
We show that the average genus of G is no less than , where is the number of vertices of degree 2 in G. This improves a lower bound of Chen, Gross and Rieper.Missing: unsolved | Show results with:unsolved