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
1
vote
1
answer
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 ...
- 127
1
vote
0
answers
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
1
answer
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 ...
- 11
0
votes
0
answers
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 ...
- 121
1
vote
0
answers
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 ...
- 11
0
votes
1
answer
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 ...
- 321
1
vote
0
answers
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 ...
- 801
2
votes
1
answer
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 ...
- 2,207
3
votes
1
answer
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 ...
- 61
1
vote
1
answer
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
1
answer
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 ...
- 103
1
vote
0
answers
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 ...
- 1,309
2
votes
0
answers
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 ...
user931598
0
votes
0
answers
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-...
- 1
0
votes
1
answer
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 ...
- 337
2
votes
1
answer
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 ...
- 91
5
votes
0
answers
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$.
...
- 2,014
5
votes
1
answer
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" ...
- 821
2
votes
1
answer
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 ...
5
votes
0
answers
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 ...
- 524
0
votes
0
answers
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?
- 65
0
votes
1
answer
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?
...
- 65
2
votes
1
answer
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 ...
- 65
1
vote
2
answers
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
2
answers
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$?
- 177
2
votes
1
answer
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 ...
3
votes
2
answers
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 ...
- 177
1
vote
1
answer
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 ...
- 177
0
votes
1
answer
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?
- 481
3
votes
1
answer
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 ...
- 3,381
-1
votes
1
answer
56
views
Equal degree sum of two graph shows they have equal vertex degrees??
I am looking for the answer of the question if two graphs have equal degree sum, then whether both have equal vertex degree.i.e., If $G$ has vertices $d_{i}$ and $G^{\prime}$ has vertices $d^{\prime}_{...
- 61
1
vote
0
answers
219
views
(path)Connectedness of a simplicial complex Vs it's $1$-skeleton
Let $\Delta$ be an abstract simplicial complex https://en.m.wikipedia.org/wiki/Abstract_simplicial_complex and $|\Delta|$ be its geometric realization.
Let $\Delta ^{(1)} :=\{F $ is a face of $\...
- 4,364
1
vote
0
answers
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.
0
votes
2
answers
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 ...
- 1,025
2
votes
1
answer
131
views
3-edge colorable cubic graph with an embedding on an orientable surface that is not 4-face colorable
Let $G$ be a simple cubic graph that is cellularly embedded on a surface such that the regions of $G$ are 4-colorable. Then by labeling the colors by the elements of $\mathbb{Z}/2\mathbb{Z} \times \...
- 5,223
3
votes
1
answer
231
views
Cycle double cover conjecture for complete graphs?
The cycle double cover conjecture states that for every bridgeless finite $G$ there is a collection of cycles $\mathcal{C}$ in $G$ such that every edges on $G$ occurs in precisely two of the cycles in ...
- 5,223
0
votes
1
answer
664
views
A sufficient condition for planar graph
Let $G$ a graph with $v$ vertices and $e$ edges.
Right, I know that if $e>3v-6$ then $G$ is not planar.
Do you know any theorem like "If $e<f(v)$ then $G$ is planar"?
1
vote
0
answers
202
views
About "combinatorial topology", what Munkres covers and a textbook reference request
When a university says they research in "combinatorial topology" what does that mean?
I've seen a university in Country A list "combinatorial topology" in its math department's research areas, but I ...
user198044
1
vote
1
answer
74
views
Neighborhoods of a topological graph
Consider a finite connected topological graph $G$ embedded on $\mathbb{R}^2$ with standard topology. Here vertices are points, and each edge is a Jordan arc between vertices; an embedding $e: [0, 1] \...
- 1,761
8
votes
2
answers
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 ...
- 20.7k
9
votes
2
answers
667
views
Infinite graph is planar iff it can be embedded in sphere
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 ...
- 171
1
vote
1
answer
151
views
Parallel planes of minimal surface
If $S_{1}$ and $S_{2}$ are properly embedded minimal surfaces with free boundary set. If $S_{1}$ does not intersect $S_{2}$ and there exist $p_{1} \in S_{1}$ and $p_{2} \in S_{2}$ such that $dist(S_{...
- 13
0
votes
1
answer
119
views
How to find an ordering of edges incident on a fixed vertex in a plane embedding?
Suppose that we have a plane embedding $G$. Let $v$ be a vertex in $G$ with degree $d$. There exist an ordering $u_1,u_2,\ldots,u_d$ of neighbors of $v$ such that the graph is still a plane embedding ...
- 532
2
votes
0
answers
27
views
How many torus can I find as a subgraph of a complete graph?
I am wondering whether there is a way to count how many non-isomorphic torus triangulation given its vertex number.
I currently have no clue about how to solve this problem. Can anyone give some ...
- 31
0
votes
1
answer
47
views
how to show any edges of a closed surface M is on exactly two triangles of M.
I just started to learn a book about surfaces on graph, here is my definition of closed surface:
a closed surface is a collection $M$ of triangles (in some Euclidean space) such that
(a) $M$ ...
- 31
0
votes
1
answer
299
views
Minimum genus of torus necessary to embed complete graph $K_n$
You can embed complete graphs $K_1$, $K_2$, $K_3$, and $K_4$ on a genus $0$ torus (a sphere).
The minimal genus of a torus on which you can embed $K_5$, $K_6$, and $K_7$ is a $1$.
Then you need a ...
- 333
0
votes
1
answer
40
views
In community detection, can $k$-cliques overlap?
When finding communities in a network using $k$-cliques, each $k$-clique may considered a community. I have an assignment where there are many $k$-cliques that appear to overlap. Does this mean they ...
- 103
1
vote
0
answers
216
views
Graph algorithms or properties for preserving the topological sort
I got a DAG (directed acyclic graph) on which I can apply a Tsort algorithm (actually its a modified one which also makes sure to visit each node using an ascending node property) in order to ...
- 111
5
votes
1
answer
501
views
Topological embedding of graph in $\mathbb{R}^3$
I was reading the following proof of the claim that every graph can be embedded in $\mathbb{R}^3$:
https://sometimesfun.wordpress.com/2015/08/02/embedding-graphs-in-r3/
At the end, there is the ...
- 756
4
votes
1
answer
335
views
Embeddings of Complete Graphs and Their Topology
Following standard notations, we use $K_n$ to denote a complete graph with n vertices. We know that $K_1,K_2,K_3,K_4$ are planar graphs and a natural notion of vertex, edge, and face can be visualized ...
- 305