All Questions
25 questions
3
votes
1
answer
108
views
Has this random process been studied on grid graphs?
As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
- 1,951
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
2
votes
1
answer
106
views
Are zonotopes determined by their edge-graph?
General polytopes are not determined by their edge-graph (up to combinatorial equivalence). But I came accross the statement that zonotopes are determined in this way.
Question: Is this true? And ...
- 13.6k
10
votes
2
answers
1k
views
Proofs of circle packing theorem
Circle packing theorem is a famous result stating that for every connected simple planar graph $G$ there is a circle packing in the plane whose intersection graph is $G$ https://en.wikipedia.org/wiki/...
- 14.3k
4
votes
0
answers
230
views
Is this case of Barnette's Conjecture known?
Context: Barnette's Conjecture is that every bipartite cubic polyhedral graph is Hamiltonian. I have been interested by this problem for a long time, and I recently came up with a result. From my ...
- 3,499
1
vote
1
answer
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of "curves"?
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$ ...
- 111
1
vote
1
answer
393
views
Hyperbolic embedding of a directed acyclic graph defined over strings
For integer $n$ and alphabet $\Sigma$ we construct a DAG (directed acyclic graph) $G=(V,E)$ over strings $s\in\Sigma^\star$ as follows:
$$V = \{s\in\Sigma^\star\colon |s|\le n\}$$
$$E = \{(s_1,s_2)\...
- 187
9
votes
2
answers
505
views
Moore graphs and finite projective geometry
In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of ...
- 1,645
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 10.7k
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
3
votes
3
answers
330
views
Voronoi and Delaunay
Please provide some references on Voronoi and Delaunay decompositions which is mathematically written. I mean I can find several texts or links on this written for computer science students without ...
user111251
17
votes
3
answers
2k
views
Applications of Kirchhoff's circuit laws to graph theory
Is there a good survey on applications of Kirchhoff's circuit laws to graph theory or/and discrete geometry?
Examples:
Matrix tree theorem,
Squaring the square,
Electrician’s proof of Euler’s ...
- 45k
1
vote
0
answers
77
views
Non-adjacent Pair of Edges with Minimal Weight Sum
Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that ...
- 13.2k
6
votes
2
answers
400
views
Geometric dominating set: NP-complete?
Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...
- 151k
5
votes
2
answers
373
views
Genus of Tutte-Coxeter Graph
What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...
user48028
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 6,101
4
votes
1
answer
646
views
Combinatorial geodesics
[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics &...
- 9,720
5
votes
2
answers
441
views
Touching-tetrahedra graphs
Have the graphs representable by touching tetrahedra been explored?
Let $\cal T$ be a collection of tetrahedra in $\mathbb{R}^3$
with pairwise disjoint interiors.
Define a graph $G_{\cal T}$ to have ...
- 151k
3
votes
1
answer
394
views
Min Bend Orthogonal Knots
I am seeking literature on 3D orthogonal drawings of knots,
especially minimum bend drawings.
An orthogonal drawing employs segments parallel to the axes of
a Cartesian coordinate system.
A bend is a ...
- 151k
6
votes
4
answers
2k
views
Delaunay triangulations and convex hulls
This is a reference request.
I have the impression that those who work in computational geometry are accustomed to the following. You have some locally finite set of sites in $\mathbb{R}^n$ and you ...
3
votes
0
answers
142
views
Dimension of convex arrangements for hypergraphs
Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.
Has ...
- 4,586