# Questions tagged [topological-graph-theory]

For questions about topological graphs, flows, representation, planar, and book embeddings, geometric graphs, crossing numbers, coloring graphs, and other topics in topological graph theory.

88 questions
Filter by
Sorted by
Tagged with
32 views

### Chromatic Number of $S_2$

What is the largest chromatic number of all the graphs $G$ that can be embedded on $S_2$ (the double torus)? To which graph is it associated?
32 views

### What is the chromatic number of S2?

How can one find the chromatic number of the orientable surface S2 (the double-torus)? Does anyone know of an example which shows this chromatic number by giving an upper bound and a lower bound? ...
38 views

### Beauty of Spectral Graph Theory

Why would one choose to study spectral graph theory? Where can the spectrum of complete graphs, for example, be applied in real- life example or of any graph in general? A brief historical background ...
51 views

### Purpose of imbedding a group onto a surface?

I'm reading the book "Topological Graph Theory" by Gross and I've gone through a fair bit of it. It seems like the entire book is leading up to being able to imbed a group onto a surface, and I have ...
22 views

### Cycles in Plane Graphs

For a plane graph $G$, if $C$ is a cycle in $G$, can $G$ be embedded in the plane so that $C$ is the face boundary of the outer face of $G$?
27 views

### Counting Topological Sorts Of Graph With In Degree 1

I was asked this question recently and am struggling to come up with the closed form solution: How many topological sorts are there for a directed acyclic graph where each vertex only has one incoming ...
49 views

### Isomorphisms of Planar Embeddings

My question: How does one distinguish between two embeddings of the same graph on the plane? For instance, are two such embeddings considered the same if the degree sequence of their faces are the ...
52 views

### Isomorphisms of Graph Embeddings

I am having trouble understanding isomorphisms of graph embeddings. How does one distinguish between two graph embeddings on the same surface, and how does one, for example, distinguish between two ...
28 views

### Are all topological graphs geometric graphs?

A topological graph or string graph is an intersection graph of curves. Can all such curves be drawn as intersection graph of line segments?
52 views

### An extension of the Utilities Problem. (for $n$ utilities) I want to find sufficient conditions to make it work.

We know that the Utility Problem asks to connect three utilities to three houses without crossing utilities line. I can prove that there is no solution in the plane or $S^2$, but it is solvable on ...
32 views

29 views

### genus of regular bipartite graph

Is there a formula for the genus of a bipartite graph with 2 sets of m vertices, where each vertex has order 3? I.e. if m=3 this is K(3,3). But I'm interested in larger m.
87 views

### Drawing a graph with given vertices edges and face on genus 1

I want to draw a graph on the genus 1 surface. The graph has 2 vertex, 6 edges and 4 faces hence it by Euler Characteristics formula it lives on genus 1 surface. I want to add an extra condition ...
41 views

124 views

### Count of maximal sextic toroidal graphs

EDIT: Lots of pictures at Sextic Toroidal Graphs There is one graph on 7 vertices, $K_7$, which is a maximal sextic toroidal graph (genus 1). It can be drawn on a torus with no edges crossing and ...
210 views

### Infinite graph is planar iff it can be embedded in sphere

My question is about the following statement about planar graphs: A graph is planar (i.e. can be embedded in the plane) if and only if it can be embedded in the sphere $S^2$. By an embedding we ...
77 views

62 views

### How is the genus of a graph affected by the addition or removal of an edge?

If I add or remove a single edge from a graph, does the genus change by at most a constant amount? More precisely, A graph parameter is a function $f$ that maps graphs to a range $\{1, \cdots, m\}$ ...
100 views

### Equivalent arrangements of arrows [closed]

Given $n$ arrows arranged so that every arrow starts from the base of one of the arrows and ends on the base of one of the arrows, what should be meant by that two such arrangements are essentially ...
67 views

### Graph map terminology

By a directed multigraph, I mean a tuple $G= (V,E,i,t)$, where $V$ is a set of "vertices," $E$ is a set of "edges," and $i:E\to V$ and $t:E\to V$ are functions giving the "initial" and "terminal" ...
128 views

### Is there a proof that any graph is “drawable” on a 2D surface? [closed]

Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small? EDIT: No ...
117 views

### Number of non-isomorphic embeddings.

Define two embeddings of a graph on a surface to be non-isomorphic if their corresponding dual graphs are non-isomorphic. How many distinct embeddings (up to isomorphism) are there of a $3$-regular, ...
58 views

### On combinations of planar graphs of given number of vertices of given valences

Good evening, I am new at the MSE, I signed up just now, so I greet you all; please bare with the newcomer. I have a graph theory problem, which has come up in an entirely different context, a ...
2k views

### Mapping The Unit Disc To The Hemisphere?

Question: Can a disc drawn in the Euclidean plane be mapped to the surface of a hemisphere in Euclidean space ? If $U$ is the unit disc drawn in the Euclidean plane is there a map, $\pi$, which ...
37 views

### What is the topological interpretation of the girth of a graph?

So we can certainly translate a lot of graph theoretic concept into topological ones, ie) We can use the maximum Euler characteristic of a graph to find the minimal genus of a surface that admits a ...
2k views

### Find all possible topological-sortings of graph G

A topological ordering of G is an ordering of the nodes as $v_1,v_2,...,v_n$ so that all edges point "forward": for every edge $(v_i,v_j)$, we have $i<j$. Moreover, the first node in a ...
I thought of this fairly trivial inequality when thinking about the crossing number of graphs. As the title says, if you find a subgraph with a known crossing number in some graph G (say $Q_4$ for ...