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
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
2
votes
1
answer
95
views
Dipping into sets of parallel edges in graph drawings
Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
- 111
1
vote
1
answer
115
views
Bounds on lengths of boxes in bounded-degree box graphs
$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\cub}{\operatorname{cub}}$
This is a follow up and an extension of another question I asked recently.
A box graph is a graph ...
- 277
1
vote
1
answer
194
views
Bounds on lengths of intervals in bounded-degree interval graphs
A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
- 277
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 ...
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
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
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
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
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
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
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
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
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
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
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
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
1
vote
1
answer
87
views
Positive type function on open subgroup
Let $\phi: G \rightarrow \mathbb{C}$ be a continuous function. We say that $\phi$ is positive type if $\sum_{i,j=1}^{n} c_i\bar{c_j}\phi(g_{j}^{-1}g_i)\geq 0$ for all $n \in N, c_i \in \mathbb{C}, g_i ...
- 581
2
votes
1
answer
102
views
Chromatic numbers of geometric duals to a fixed graph
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 ...
- 151
1
vote
1
answer
160
views
Chordless cycles and planarity in graphs
Let $\{C(G)\}$ be the set of chordless cycles of a graph $G$. Compare the cycles pairwise. Let $\{V\}$ represent the pairs which have exactly one vertex in common; and, let $\{P\}$ represent those ...
- 11
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
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
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
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
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
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
1
vote
1
answer
116
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 ...
- 767
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
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
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
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
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
2
votes
1
answer
111
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 ...
- 1,389
1
vote
1
answer
116
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 ...
- 13.9k
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
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
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 ...
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
2
votes
2
answers
412
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
121
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 ...
- 903
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
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
2
votes
1
answer
137
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 ...
- 903
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
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
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
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
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