Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with topological-graph-theory
Search options not deleted
user 2233
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).
3
votes
Accepted
Bounds on lengths of intervals in bounded-degree interval graphs
Yes, we may take the function to be $2\Delta$.
Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum d …
- 32.1k
5
votes
Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgra...
Yes, this is true. See my paper Subgraph densities in a surface with Gwenaël Joret and David Wood. We prove that for every $s \geq 5$, the number of $s$-cliques in a graph of Euler genus $g$ is at mo …
- 32.1k
10
votes
1
answer
307
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
17
votes
Accepted
Can all crossings in a graph be moved to one point?
No, this is not always possible.
Lemma. Let $G$ be an $n$-vertex graph with at least $3n-2$ edges. Then $G$ cannot be drawn in the plane so that all crossings occur at the same point.
Proof. We make …
- 32.1k
3
votes
Accepted
Asymptotics of list size in Robertson-Seymour theorem
No, it is not linear in the genus; it is at least exponential in $g$. See for example this answer by David Eppstein.
- 32.1k
4
votes
Accepted
Construction of planar embedding
Here are some more details. We will prove the following stronger claim.
Theorem. Let $G$ be a planar graph with $n$ vertices and maximum degree 4. For every planar embedding $\Gamma$ of $G$, there …
- 32.1k
9
votes
Embedding planar graphs into the grid
As far as I understand, I think you have misstated Valiant's result.
Regarding $1$, yes the embedding is assumed to be planar, with the edges constrained to follow the 'edges' of the grid. This is ca …
- 32.1k
5
votes
Example to show pairwise crossing number is not equal to crossing number
As far as I know this is still an open problem. It is listed as an open problem in the paper Which crossing-number is it anyway? by Pach and Tóth, and also in the introduction of this more recent sur …
- 32.1k
8
votes
Accepted
Why are graph embeddings defined the way they are?
I can think of a couple of other reasons. The first is algorithms. Many algorithmic problems become easier if we are told that the input graph is embeddable on a surface. As a trivial example: the …
- 32.1k
31
votes
Obstructions for embedding a graph on a surface of genus g
I'll just remark that the fact that every surface has a finite number of excluded minors (and also topological minors) does not require the full strength of the Graph Minors Theorem. Indeed, the proo …
- 32.1k
3
votes
Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to...
There should be a nice proof, but here is a reference that proves something stronger and weaker. This paper by de Graaf and Schrijver proves that every graph embedded on the torus with face-width at …
- 32.1k
9
votes
Gauss-Bonnet Theorem for Graphs?
There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the combinatorial curvature at a vertex $x$ of $G$ is
$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)} …
- 32.1k
11
votes
Why are planar graphs so exceptional?
Another (less known) characterization of planar graphs is Schnyder's theorem,
which characterizes planar graphs according to
order dimension. That is, a graph is planar if and only if its incidence …
- 32.1k