# 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.

90 questions
Filter by
Sorted by
Tagged with
1answer
40 views

### Automorphisms of directed surface graphs

I came across a problem where I need to be able to find automorphisms of a directed graph embedded on a surface. WLOG, I can assume the surface is a plane (if that is helpful). Normally, a graph ...
0answers
40 views

### What is Euler's Formula when 2­-cell embedding condition was removed?

It is well known that Euler's Formula for genus $\gamma$: For every 2­-cell embedding of a graph on a surface with genus $\gamma$, the numbers of vertices, edges, and faces satisfy $n-e+f=2-2\gamma$. ...
1answer
73 views

### Construct the smallest graph homeomorphic to a given graph by smoothing

The homeomorphism class $\mathcal{H}(G)$ of a graph $G$ is the set of isomorphism classes of graphs that are topologically homeomorphic to $G$. It is natural to ask: Is there a "smallest" ...
1answer
82 views

### Bijective projection from a unit disk to a unit sphere

Is there any proper method that makes conformal one-to-one mapping (preserving the angles) from a unit disk to a unit sphere? I know with simple stereographic projection you can project a unit disk to ...
0answers
80 views

### Chromatic Number Range of Dual Graphs?

A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$. Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$. Using $\chi$ to denote ...
0answers
37 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?
1answer
49 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? ...
1answer
86 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 ...
2answers
56 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 ...
2answers
73 views

### For any cycle, must there exist a planar graph embedding with it as the face boundary?

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$?
1answer
101 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 ...
2answers
124 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 ...
1answer
114 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 ...
1answer
35 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?
1answer
86 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 ...
1answer
40 views

0answers
34 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.
2answers
138 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 ...
1answer
52 views

2answers
180 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 ...
2answers
370 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 ...
1answer
90 views

1answer
74 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\}$ ...
1answer
103 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 ...
0answers
69 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" ...
1answer
138 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 ...
0answers
130 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, ...
0answers
62 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 ...
3answers
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 ...