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
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
1
vote
1
answer
283
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,...
- 2,371
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
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
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 ...
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 ...
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
2
votes
0
answers
215
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 ...
- 884
2
votes
1
answer
238
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? ...
- 13.9k
2
votes
1
answer
401
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 ...
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
1
vote
2
answers
800
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 ...
- 123
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