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 answers only
not deleted
user 6094
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
votes
Given the skeleton of an inscribed polytope. If I move the vertices so that no edge increase...
This addresses only the $n=m=2$ case.
Break the polygon $P$ into an open polygonal chain with the same lengths
as $P$. Place the chain
in a large-radius circle, and shrink the radius until the chain c …
- 151k
1
vote
Accepted
Surfaces generated by minimum-weight triangulations
My guess is that a minimum edge-weight triangulation would not in general lead to a minimum-area surface. Instead a minimum-area triangulation might.
There is a considerable literature on triangulatio …
- 151k
1
vote
Clustering of vertices in an $n$-dimensional cube
Just an illustration of
@RichardKlitzing's construction in 3D:
His $n+1 = 4$ layers are:
$$
v_1 \;,\; \{v_2,v_4,v_5\} \;,\; \{v_3,v_8,v_6\} \;,\; v_7
$$
- 151k
2
votes
Accepted
Squaring a square and discrete Ricci flow
My question is answered in Lovász's book:
Lovász, László. Graphs and Geometry. Vol. 65. American Mathematical Soc., 2019.
p.82:
Theorem 6.2. Every planar map in which the unbounded country is a qua …
2
votes
Squaring a square and discrete Ricci flow
I just found this citation, not cited in the AMS Notices paper (but I cannot yet access the Israel J Math paper itself):
Schramm, Oded. "Square tilings with prescribed combinatorics." Israel Journal …
8
votes
Proofs of circle packing theorem
I can recommend Sariel Har-Peled's exposition in supplemental
Chapter 15 of his book
Geometric Approximation Algorithms.
Ch15 PDF download.
He emphasizes angles via a "whac-an-angle" game.
He acknowle …
- 151k
10
votes
Which curves and surfaces are realizable by linkages? references?
Erik Demaine and I also included a proof for $d=2$ in Geometric Folding Algorithms:
Linkages, Origami, Polyhedra, Chapter 3.
There we asked if there is a planar (non-crossing) linkage that
"signs you …
- 151k
10
votes
A tree with prime vertices
Not an answer, just a drawing of the tree including the
OP's $2 \rightarrow 191$ path:
- 151k
5
votes
Accepted
Is the acyclic chromatic number bounded in terms of the book thickness?
I believe that "book thickness bounds the acyclic chromatic number" was
established in this paper:
Dujmovic, Vida, Attila Pór, and David R. Wood. "Track layouts of graphs." Discrete Mathematics an …
- 151k
2
votes
Accepted
Uniqueness constraints for Delaunay triangulation
I think it is well-understood that "no four points cocircular" avoids Delaunay triangulation degeneracies. It is also well-understood that one can have four cocircular points that don't cause any dege …
- 151k
7
votes
Accepted
Convex triangulations
Nice idea but it seems not to always exist:
Point $4$'s star is reflex at $3$,
Point $3$'s star is reflex at $4$.
Here's an argument that those are the only two triangulati …
- 151k
2
votes
Polygonal paths and polygons with prescribed set of vertices
This paper addresses similar (but I don't think identical) questions.
In any case, a key search phrase is covering path.
Dumitrescu, Adrian, Dániel Gerbner, Balázs Keszegh, and Csaba D. Tóth. "Cov …
- 151k
4
votes
Polygonal paths and polygons with prescribed set of vertices
Not an answer, just an illustration for $6$ points, $0 \le x+y \le 2$.
$A,B,C$: Point $3$ cannot connect to $1$ or $6$, so it must connect to
$2,5$ or $4,5$ or $2,4$.
$B$: Point $6$ is now …
- 151k
2
votes
Accepted
Relation between vertex connectivity and independent set
Addressing just this:
"Given a graph 𝐺 does there exist any command in SageMath or in any other software which can say the minimum separating set of a graph?"
This set is known as a minimum ve …
- 151k