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 graph-theory
Search options not deleted
user 56833
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
4
votes
0
answers
137
views
Can the vertices of a planar graph of min degree 3 be covered with edges of average weight (...
Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.
If not, what is the smallest n so that e …
- 111
5
votes
0
answers
197
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small ($o(|V(G)|$) subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an endp …
- 111
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
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is...
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ i …
- 111
1
vote
0
answers
77
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of edg …
- 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 e …
- 111
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 abo …
- 111