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).
70
questions
10
votes
1
answer
259
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 ...
3
votes
2
answers
105
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 ...
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. ...
3
votes
1
answer
133
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: ...
5
votes
0
answers
79
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 ...
6
votes
0
answers
132
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-...
4
votes
0
answers
58
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 ...
4
votes
1
answer
185
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., ...
10
votes
1
answer
302
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$. ...
4
votes
1
answer
363
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$....
5
votes
1
answer
130
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 ...
1
vote
0
answers
32
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" ...
9
votes
3
answers
1k
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 ...
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 ...
5
votes
1
answer
476
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 ...
6
votes
0
answers
74
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 ...
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 ...
1
vote
1
answer
73
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 ...
2
votes
1
answer
100
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 ...
1
vote
1
answer
136
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 ...
3
votes
0
answers
149
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$$...
3
votes
0
answers
93
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 $...
1
vote
0
answers
103
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-...
24
votes
1
answer
565
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 ...
12
votes
0
answers
206
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 ...
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 ...
1
vote
1
answer
114
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 ...
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
votes
1
answer
103
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 ...
10
votes
1
answer
360
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 ...
4
votes
0
answers
193
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
votes
1
answer
255
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$...
2
votes
1
answer
110
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
vote
1
answer
114
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 ...
4
votes
2
answers
229
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 ...
12
votes
3
answers
576
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 ...
2
votes
0
answers
27
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 ...
4
votes
1
answer
523
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, ...
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 ...
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 ...
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 ...
2
votes
2
answers
350
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
115
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 ...
4
votes
2
answers
254
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 ...
47
votes
4
answers
9k
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, ...
1
vote
0
answers
116
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 ...
2
votes
1
answer
131
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 ...
3
votes
1
answer
198
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 ...
2
votes
4
answers
11k
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
603
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 ...