# Tagged Questions

**6**

votes

**2**answers

110 views

### Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes.
What is the maximum number of edges of a linklessly embeddable graph?
A more general question is the following. Given $\mu$ what is the maximum number of edges of ...

**0**

votes

**0**answers

44 views

### Paths on Cartesian products of graphs satisfying linear constraints

Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ ...

**0**

votes

**1**answer

55 views

### mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations.
Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...

**7**

votes

**2**answers

270 views

### Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node
connected to its four neighbors, with the top row connected to the bottom,
and the right column connected to the left.
Suppose ...

**6**

votes

**1**answer

154 views

### Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...

**1**

vote

**0**answers

43 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...

**5**

votes

**2**answers

201 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 ...

**5**

votes

**3**answers

276 views

### How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

Consider a graph $G$ with nonnegative edge weights.
Question: In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?
...

**13**

votes

**3**answers

658 views

### Are infinite planar graphs still 4-colorable?

Imagine you have a finite number of "sites" $S$ in the positive quadrant
of the integer lattice $\mathbb{Z}^2$,
and from each site $s \in S$, one connects $s$ to every lattice point to which it
has a ...

**3**

votes

**1**answer

282 views

### Geodesic convex hulls in a graph; and their properties

This question asks for an analog of the convex hull in a graph that parallels
(as far as possible) convex sets in Euclidean space.
Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...

**4**

votes

**0**answers

221 views

### Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset S of the xy-plane is star-convex if there is ...

**1**

vote

**2**answers

234 views

### Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues and combinatorial properties of ...

**5**

votes

**2**answers

186 views

### Embedding points in 2D based on distance estimates?

Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose ...

**19**

votes

**2**answers

773 views

### Erdős, Harary, Tutte's “dimension of graph”: Progress in last 48 yrs?

I just ran across this delightful paper by an amazing triumvirate:
Paul Erdős, Frank Harary, and William Tutte. "On the dimension of a graph." Mathematika 12.118-122 (1965): 20.
(Cambridge link)
...

**11**

votes

**0**answers

346 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 ...

**4**

votes

**0**answers

119 views

### Graph drawing maximizing the volume of the convex hull

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$.
An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that ...

**1**

vote

**0**answers

115 views

### Spectrum of Combinatorial Laplacian

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices?
In particular:
Let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...

**4**

votes

**1**answer

399 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 ...

**0**

votes

**1**answer

214 views

### Is this bounded?

May be better to ask for help here. Let $v_{1}$, $v_{2}$, $\ldots$, $v_{m}$ be the vertices of a
convex polygon in the plane and $v_{m+1}$ be a vertex in the interior
of the convex polygon. Connect ...

**3**

votes

**2**answers

317 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 ...

**2**

votes

**1**answer

191 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 ...

**2**

votes

**2**answers

540 views

### maximum number of shortest path among a set of n triangle obstacles

Assume that we have a two distinct points. The number of shortest path between these two points is one. When we add a triangle obstacle to the plane and this triangle intersects the line connecting ...

**8**

votes

**3**answers

596 views

### Small 4-chromatic coin graphs

A coin graph is a graph that can be represented by a set of disjoint, except possibly touching, unit disks in the plane (i.e. the disks are the vertices and the edges correspond to the pairs that ...

**4**

votes

**4**answers

939 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 ...

**6**

votes

**3**answers

249 views

### Minimum separating subdivision in Plane

Hi
I was thinking about the following problem:
Given a planar Graph embedded in the plane and a set of points $P$ contained in the faces (no face contains more than one point) I want to determine ...

**1**

vote

**1**answer

235 views

### Characteristics of locally triangle-free graph

Hi
I am given a triangulation $T $ of a set of points $S $ in the plane and a disk $D$ which doesn't contain any triangle. If I now look at the subgraph $G(V,E)$ of $T $ whose vertices are the points ...

**3**

votes

**1**answer

268 views

### Enumerating Connected Circle Graphs

Hi
A circle graph is defined as the intersection graph of a set of chords of a circle.
I'm interested in any information which might help to enumerate connected circle graphs.
Thanks
Andy

**17**

votes

**6**answers

1k views

### Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting
each integer lattice point
in the 2D square grid $[0,n]^2$
to each of its (at most) four neighbors, {N,S,E,W}.
Within each of the $n^2$ unit cells of ...

**7**

votes

**3**answers

439 views

### “incidental” intersections of a complete graph in the plane

Given a complete graph of n vertices (no three of which are no collinear) in the plane and straight edges, what is the maximal possible number of "incidental intersections" of edges, i.e., number of ...

**3**

votes

**0**answers

125 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 ...

**10**

votes

**1**answer

390 views

### Random geometric graphs and spanners

I would grateful to learn of work mixing
random geometric graphs with random graphs under
the
Erdős-Renyi model, and in particular concerning spanners.
Select $n$ points uniformly at random from the ...

**5**

votes

**2**answers

467 views

### Generalization of Hamiltonian cycles to “Hamiltonian spheres”

One possible generalization of a Hamiltonian cycle in a triangulated plane graph is what could be
called a Hamiltonian sphere: a collection of triangles within a simplicial complex in $\mathbb{R}^3$
...

**15**

votes

**3**answers

1k views

### Gauss-Bonnet Theorem for Graphs?

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an n-cycle has χ = 0 and K4 has χ = –2.
Is there an analog for the ...

**6**

votes

**3**answers

673 views

### Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II

For some context see Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
As per Noah's answer and JBL's comment this was false as stated. However, I think the following ...

**9**

votes

**1**answer

422 views

### Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance

Problem: Consider a random walk on the lattice $\mathbb{Z}^2$ where on each iteration a particle either stays at its current location or moves to a neighboring vertex with probability 1/5. We start ...

**4**

votes

**4**answers

1k views

### Number of spanning trees in a grid

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have ...