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).
77 questions
47
votes
4
answers
10k
views
Why are planar graphs so exceptional?
As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
- 12.6k
25
votes
1
answer
596
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 ...
- 2,242
24
votes
3
answers
2k
views
Gauss-Bonnet Theorem for Graphs?
One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$.
Is there an analog for the ...
- 151k
21
votes
3
answers
2k
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 ...
- 1,180
20
votes
4
answers
2k
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 ...
- 24.8k
18
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,180
14
votes
5
answers
669
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 $...
- 7,857
13
votes
1
answer
718
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 ...
- 5,898
13
votes
0
answers
212
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 ...
- 1,190
12
votes
3
answers
582
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 ...
- 18.7k
11
votes
2
answers
2k
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 ...
- 111
10
votes
2
answers
598
views
Is there a "simplest" way to embed a graph in 3-space?
I consider embeddings of graphs into 3-space with edges embedded as arbitrary curves. In the simplest (non-trivial) case the graph $G$ is a cycle or union of cycles, in which case the embeddings can ...
- 13.6k
10
votes
3
answers
460
views
Do triple-linked graphs exist?
Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
- 13.6k
10
votes
1
answer
369
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 ...
- 175
10
votes
1
answer
312
views
Is this drawing of $K_{4,4}$ knotted?
Let $A$ and $B$ be skew lines in $\mathbb{R}^3$. Choose four points $a_1, a_2, a_3, a_4$ on $A$ and four points $b_1, b_2, b_3, b_4$. For all $i,j \in [4]$ draw a line segment from $a_i$ to $b_j$. ...
- 32.1k
9
votes
2
answers
12k
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 ...
- 93
9
votes
3
answers
2k
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 ...
- 903
9
votes
1
answer
489
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)\...
- 3,626
9
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, ...
- 1,324
8
votes
2
answers
615
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 ...
- 83
8
votes
2
answers
1k
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 ...
- 37.7k
8
votes
2
answers
369
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.
- 461
7
votes
2
answers
4k
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$ ...
- 4,015
6
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 ...
6
votes
1
answer
142
views
Embedding linklessly embeddable graphs without Borromean rings
A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph.
Now, I can think of another ...
- 13.6k
6
votes
0
answers
142
views
Graph-theoretic quasi-crystals?
I have recently been interested in the following purely graph-theoretic notion that weakens the assumption of transitivity in a similar way to how quasi-crystals have "(possibly) aperiodic long-...
- 775
6
votes
0
answers
78
views
Implications of combinatorial results towards discrete function theory on circle packings
Spurred primarily by a conjecture of Thurston in 1985, there was a series of developments in creating a "discrete analytic function" theory for maps between circle packings of complex ...
- 161
5
votes
1
answer
479
views
Can all crossings in a graph be moved to one point?
Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
- 4,829
5
votes
2
answers
373
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 ...
user48028
5
votes
0
answers
83
views
When does the ΔY-family of a simple graph contain multigraphs?
Given a graph $G$, its ΔY-family is the smallest family of graphs that contains $G$ and is closed under ΔY- and YΔ-transformations.
Since YΔ-transformations can introduce multi-edges, the ΔY-family of ...
- 13.6k
4
votes
2
answers
232
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 ...
- 13.9k
4
votes
1
answer
214
views
Find all 2-planar drawings of $K_6$ and $K_7$
A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per
edge.
It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$.
Angelini P., Bekos M. A., ...
- 1,851
4
votes
2
answers
266
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 ...
user76479
4
votes
1
answer
393
views
Example to show pairwise crossing number is not equal to crossing number
A common point of two edges in a graph drawing that is not an incident vertex is called a crossing.
The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of $G$....
user39815
4
votes
1
answer
195
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 $...
- 283
4
votes
1
answer
539
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, ...
user39815
4
votes
0
answers
65
views
Which cellular embeddings of Eulerian graphs have bipartite duals?
It is well-known that a plane graph $G$ is Eulerian if and only if its (geometric) dual $G^*$ is bipartite.
I am interested in generalisations of this result to cellular embeddings of Eulerian graphs ...
- 191
4
votes
0
answers
200
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,506
3
votes
1
answer
5k
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 ...
- 191
3
votes
2
answers
135
views
Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?
For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
- 31
3
votes
1
answer
162
views
Conditions on graphs to assure unique embedding on a fixed genus surface
The classical Whitney Theorem in low topological theory/graph theory states that every 3-connected planar graph is uniquely embeddable (up to orientation) on the sphere.
My question is the following: ...
- 1,561
3
votes
1
answer
215
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 ...
- 903
3
votes
0
answers
150
views
Genus of the graph complement
Suppose a simple undirected graph $G$ with $n$ vertices has (minimum) genus $g$. What is the genus of its complement?
My intuitive guess is that the answer is something like
$$\text{genus of }K_n - g$$...
- 41
3
votes
0
answers
94
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 $...
- 767
3
votes
0
answers
129
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 ...
3
votes
0
answers
219
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 ...
- 2,830
2
votes
4
answers
12k
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 ...
2
votes
1
answer
319
views
Why are graph embeddings defined the way they are?
In my recent question I asked about a proof for the fact that the dual of a dual graph embedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...
- 2,830
2
votes
1
answer
114
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 ...
- 563
2
votes
1
answer
270
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$...
- 24.8k