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.
3
votes
Efficient Hamiltonian cycle algorithms for graph classes
There are linear-time algorithms based on Whitney's and Tutte's theorems on 4-connected
planar graphs:
Asano, Takao, Shunji Kikuchi, and Nobuji Saito. "A linear algorithm for finding Hamiltonian cycl …
- 4,713
5
votes
determining k-edge-connectivity of a graph
Generally $k$-connectivity is computed using max-flow min-cut algorithms. I cannot quote you complexities off the top of my head, but you should be able to find the number of edges that disconnect an …
- 1,446
5
votes
Higher-dimensional Fáry's theorem?
In the paper by Archdeacon et al.,
"Corollary 1.2 proves Grünbaum's conjecture for triangulations of the torus."
Dan Archdeacon, C. Paul Bonnington, Joanna A. Ellis-Monaghan.
"How to Exhibit Toroidal …
- 1,446
4
votes
8
votes
Generalizations of the four-color theorem
There is a recent generalization to $k$-uniform hypergraphs that are
embeddable in $\mathbb{R}^d$ without edge intersections.
"For $k=d=2$ the problem specializes to graph planarity":
Carl Georg Heis …
- 4,713
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
5
votes
How to find central vertex in a graph?
Mathematica has a function GraphCenter[] that computes the center of a graph (the set of vertices with minimum eccentricity--exactly your definition).
You can find a description in the documentation h …
- 4,713
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 …
- 151k
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 …
- 151k
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