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

104 questions
Filter by
Sorted by
Tagged with
1 vote
109 views

### Special Book Embeddings

I am taking a course on Topological Graph Theory, where we have looked into the topic of Book Embeddings. The particularly interesting ones were Book Embeddings with thickness 2. This essentially ...
1 vote
31 views

### Structural characterizations of planar graphs

I'm looking for as many characterizations of planar graphs, preferably those that are more `structural'. Wagner's and Kuratowski's results get close, but the characterizations of Whitney and Maclane ...
1 vote
62 views

### Binary optimization on a direct-acyclic-graph(DAG)

Given a DAG $G$, each edge of the DAG $e \in E(G)$ relates to a attribute $w_e \in \{-1, 1\}$ Try to find the optimized attribute setting $[w_e]$ s.t. the cost function $$\sum_{e\in E(G)} w_e$$ is ...
16 views

### How can i represent the possible paths for this structure?

So for a T-junction i have this: Image source: J. Rivera, J. Leimhofer, and H.-A. Jacobsen, “OpenGridMap: Towards Automatic Power Grid Simulation Model Generation from Crowdsourced Data,” The ...
1 vote
49 views

### How to construct a graph H (with the least number of nodes) that has a subgraph that is isomorphic to each graph in a given set?

Given a finite set of target graphs $\{G_1, G_2, ...\}$ (~20 unique graphs), how to find a graph $H$ (with the lowest number of nodes), that has a subgraph that is isomorphic to each target graph in ...
39 views

### Analyse the dimension by putting a graph into euclidean space without edge intersection

Say we have a graph which has maximum $k$-clique as its subgraph. Let us try to put each vertices of the graph into Euclidean space without having any intersection of edges. Note that we assume that ...
1 vote
51 views

### almost planar graphs are minor closed

I'm trying to show that almost planar graphs are minor-closed. For that I need to show if $G-e$ is planar, then $G/e$ is almost planar (and vice versa). My approach: I'm trying to show this using the ...
51 views

### What's wrong with my map of the hemicube?

Reading from The Foundations of Topological Graph Theory by Bonnington and Little, a map is defined as a set $X$ with two permutations $\pi$ and $\varphi$ such that the orbits of $\pi$ are all of size ...
27 views

### Does projective-planarity with low facewidth always imply near-planarity of a graph?

Context: I have a large collection of nonplanar graphs, all of which I know to be projective-planar with representativity (also known as facewidth) exactly 2. I suspect that all of these graphs ...
1 vote
70 views

### Upper bound for the degeneracy of maximal planar bipartite graphs

I understand that the degeneracy of a complete bipartite graph $K_{m,n}$ is $\delta(K_{m,n})=\min\{m,n\}$. However, I am trying to look bounds for the degeneracy of maximal planar bipartite graphs. I ...
1 vote
82 views

### What is the connection between adjacency matrix and topological measures

What are the connections we can draw from a graph's adjacency matrix and topological measures that can be defined on the network induced by the graph? For example can we detect "holes" in a ...
1 vote
39 views

### Can a graph with circumference $n$ always be $n$-colored? [duplicate]

Say a simple graph $G$, which is not necessarily planar, has a circumference of $n$ (that is to say, there exists a subgraph $C_n$ where $n$ is maximized). Is it sufficient to say that the graph can ...
21 views

### Minor of an acyclic finite graph is acyclic as well

Let $G$ be a graph with no cycles. We want to either prove or disprove that any minor graph of $G$ is either acyclic or cyclic. My idea: If $G$ is cyclic, all connected components are trees. Choose ... 53 views

### Are all finite graphs that cannot embed in any non-orientable surface planar?

There exist graphs which don't have a 2-cell embedding in any non-orientable surface (take $C_n$, for example). Is it true that any finite graph with this property must be planar? Define the non-...
124 views

### Why Frucht's Theorem is only true for Finite Groups?

The statement of the Frucht's Theorem as follows: "Every Finite Group is Automorphism Group of some graph." The proof involves a result that the group of color preserving Automorphisms of a ...
216 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 ...
200 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$. ...
251 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" ...
312 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 ...
224 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 ...
58 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?
105 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? ...
320 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 ...
1 vote
67 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 ...
1 vote
301 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$?
190 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 ...
600 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 ...
1 vote
286 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 ...
44 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?
197 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 ...
56 views

1 vote
57 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.
199 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 ...
131 views

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