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).
22 questions with no upvoted or accepted answers
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
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
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
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
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
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
0
answers
49
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 ...
- 767
2
votes
0
answers
28
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
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
1
vote
0
answers
42
views
What lower bounds are known for pair crossing number and related questions in multigraphs?
So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside.
What do we know ...
- 111
1
vote
0
answers
97
views
Problem related to crossing number
Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$.
Denote $\delta(v)$ the set of edges with one ...
- 111
1
vote
0
answers
48
views
Assessing the homogeneity of a dendrogram
I'm developing a model that organises items of different classes into a dendrogram, like the one here:
Consider the next dendrogram, it is clearly more homogeneous, i.e. verteces of the same colour ...
1
vote
0
answers
33
views
Arranging bounded degree graphs into grids with few edges connecting horizontal and vertical lines
The following question arose when I was trying to find explicit topological embeddings of bounded degree graphs into $\mathbb R^3$ which match (asymptotically) the minimal possible "volume" ...
- 743
1
vote
0
answers
109
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-...
- 461
1
vote
0
answers
123
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 ...
- 903
0
votes
0
answers
23
views
Building hypercubes from the bottom up
let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices.
setting
$\mathbb{H}^0 := V$, i.e. ...
- 13.2k
0
votes
0
answers
56
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,089