# Questions tagged [topological-graph-theory]

Graph theoretical questions with a topological flavour. For example, graphs on surfaces, spatial embeddings, and geometric graphs. Use the graph-drawing tag for questions specific to graph drawing (e.g. crossing numbers).

51
questions

**1**

vote

**0**answers

44 views

### What is known about this generalization of planar dual?

So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...

**22**

votes

**1**answer

424 views

### Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...

**3**

votes

**0**answers

62 views

### The pagenumber of subdivision of a complete graph

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The book thickness $...

**12**

votes

**0**answers

124 views

### Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...

**2**

votes

**0**answers

36 views

### Book thickness of covering graph II

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a ...

**1**

vote

**1**answer

108 views

### Bookthickness of covering space

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a ...

**0**

votes

**0**answers

55 views

### Are total graph of power of cycles homeomorphic to powers of cycles?

Is the total graph associated to powers of cycles homeomorphic to powers of cycles themselves?
I think yes, because the total graph associated to cycles is homeomorphic to cycles(i think?)So, does ...

**2**

votes

**1**answer

77 views

### Genus for specific family of graphs

We are looking for graphs with certain properties that have a specific genus. We constructed a simple family, but now realised that we actually only have an upper bound for the genus. Is there an easy ...

**10**

votes

**1**answer

230 views

### Orientations of Planar Graphs

Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient
the edges of $G$ such that for each vertex $v$, there are no
three ...

**18**

votes

**4**answers

839 views

### Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. What is its graph genus (orientable or non-orientable)?
The best I could get by trial and error is an embedding ...

**4**

votes

**0**answers

162 views

### Similarities between isomorphism classes of homeomorphic directed graphs

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by ...

**2**

votes

**1**answer

105 views

### Maximum genus of an abstract “cycle complex”

Let us define an abstract "cycle complex" as the following combinatorial object: it is $(V, C)$, where $V$ is a set of $n$ nodes, $C$ is a set of $c$ cyclically ordered subsets of $V$, each of size ...

**1**

vote

**1**answer

100 views

### On graph imbedding genus clarification

Given a graph the minimum genus $g$ is the minimum number of handles needed so that there an imbedding of the graph on the surface with no edge crossings.
If the graph is of genus $g$ then is there ...

**4**

votes

**2**answers

165 views

### Number of non-equivalent graph embeddings

Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings.
Is there a way ...

**2**

votes

**1**answer

189 views

### Loop of crosscaps and Euler characteristic

The first picture below has $v=12$ vertices, $e=16$ edges, and seems to have $k=4$ crosscaps (denoted by something like $\oplus$). The number of faces $f$ should satisfy
$$v-e+f=2-k$$
which gives $f=2$...

**2**

votes

**0**answers

20 views

### (Cyclic) edge-connectivity for lifts of voltage graphs?

Can someone point me in the direction of what's known about edge connectivity (or, ideally, cyclic edge connectivity) of graphs which are lifts of voltage graphs? It seems like someone should have ...

**2**

votes

**2**answers

233 views

### Decomposing a graph into n-cycles [closed]

Suppose I have a strongly $k-regular$ graph $G$, of size $v$, where every vertex is $N>0$ $n-cycles$, for $at least$ one value of $n$ that divides $v$. Can we cut edges from $G$ in such a way ...

**2**

votes

**1**answer

101 views

### Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...

**3**

votes

**2**answers

200 views

### Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...

**1**

vote

**0**answers

107 views

### Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In particular i'm interested in the construction Valiant describes to prove that it is possible to ...

**2**

votes

**1**answer

120 views

### VLSI circuit embeddings

In the following paper by Valiant
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...

**3**

votes

**1**answer

165 views

### Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...

**7**

votes

**3**answers

478 views

### Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**8**

votes

**2**answers

508 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**4**

votes

**1**answer

347 views

### Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path.
A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...

**12**

votes

**5**answers

535 views

### Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that
$G_n$ has $n$ vertices,
the number of edges of $G_n$ is $O(n)$, and
the crossing number of $G_n$ is $\Omega(n)$?
In particular, do random $...

**1**

vote

**1**answer

182 views

### Two definitions of genus for circle graphs

In the (very nice) article of Goldstein and Turner untitled Applications of Topological Graph Theory to Group Theory, the following definitions can be found:
Definitions: A circle graph is a pair $(G,...

**5**

votes

**2**answers

309 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**4**

votes

**1**answer

165 views

### genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each $...

**3**

votes

**0**answers

117 views

### Computing with Graphs in Surfaces

I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it.
I am currently working on a research project ...

**2**

votes

**5**answers

8k views

### Graduate Schools for Graph Theory [closed]

I am a rising senior in a small liberal arts college, and I was wondering if anyone could suggest me good graduate schools for graph theory. My only exposure to graph theory has been the intro graph ...

**8**

votes

**2**answers

941 views

### Spanning trees of plane graphs containing an edge of every face

I feel sure this must be known, but can I find it??
Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the ...

**2**

votes

**0**answers

198 views

### Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length?
By polyhedral embedding I mean an embedding of the graph on a ...

**2**

votes

**1**answer

230 views

### Maximum fixed genus Bipartite graphs

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$.
What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? ...

**2**

votes

**1**answer

375 views

### Obstructions to genus $g+1$ bipartite graph having genus $g$

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices.
Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...

**9**

votes

**1**answer

412 views

### Flow on Infinite Graphs

Assume you have a simple, infinite graph $G$ with bounded degree (there is an upper bound for the degree of the nodes). Choose an arbitrary vertex $x\in V(G)$ and consider
$$
G_{n}:=\{x\in G:d(x_0,x)\...

**12**

votes

**3**answers

550 views

### Can we map every graph in the plane such that all induced cycles selfintersect?

Suppose we have a graph G. Is it true that we can map its vertices to the plane such that when connecting neighboring vertices with segments, then any induced cycle of G that has length at least 4 ...

**8**

votes

**2**answers

331 views

### Spectral techniques for genus of a graph

A generic question:
are there any spectral techniques to estimate the genus of a graph? I am interested in complete balance multipartite graph.

**15**

votes

**2**answers

1k views

### The Klein bottle and the Heawood Conjecture

Let $\Sigma_g$ be a surface of genus $g$. The Heawood Conjecture gives a closed formula in one variable, $\chi$ (the Euler characterstic of $\Sigma_g$), for the minimal number of of colors needed to ...

**1**

vote

**1**answer

267 views

### Why are graph imbeddings defined the way they are?

In my recent question I asked about a proof for the fact that the dual of a dual graph imbedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...

**2**

votes

**0**answers

211 views

### Double duality for “geometrically defined” graph imbeddings

I am studying imbeddings of (connected, undirected, unweighted, multi-)graphs on oriented surfaces of arbitrary genus, and I am searching for a reference for the statement that the dual of the dual ...

**21**

votes

**3**answers

1k views

### Obstructions for embedding a graph on a surface of genus g

Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings.
Is the ...

**13**

votes

**1**answer

627 views

### Homotopy theory for spanning trees of a graph

I am studying a paper of L. Lovász, ``A homology theory for spanning trees of a graph,'' but professor Babai has told me that Lovász later realized that this work is better framed in the language of ...

**11**

votes

**2**answers

1k views

### Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long?

If we are given a graph embedded on a torus, with the following properties, what is the minimum number of edges it can have?
Any noncontractible loop is comprised of at least n edges.
Any ...

**7**

votes

**2**answers

3k views

### Singular homology of a graph.

By a graph I will understand an undirected graph without multiple edges or loops. By a morphism of graphs I will understand a map $f$ between the underlying sets of vertices, such that if $x$ and $y$ ...

**5**

votes

**2**answers

9k views

### Reporting all faces in a planar graph

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...

**8**

votes

**0**answers

1k views

### Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...

**4**

votes

**3**answers

1k views

### Is there a bipartite analog of graph theory?

I would like to compile a list of questions about graphs that have a non-trivial analogs for bipartite graphs.
Let me give the following examples:
Cycle vs Even cycle. Most questions about cycles in ...

**3**

votes

**1**answer

3k views

### ? A graph is four colorable if and only if it is planar.

? A graph is four colorable if and only if it is planar.
Is this true, I know that if a graph is planar it is four colorable, but is it true that if a graph is four colorable it must be a planar ...

**1**

vote

**2**answers

656 views

### How many dimensions I need to embed a graph? [duplicate]

Possible Duplicate:
What is the max number of points in R^3, interconnected by generic curves?
Given a set of points connected by edges lying on an euclidean plane,
I'd like to find which is the ...