Tagged Questions

5
votes
0answers
59 views

Does this graph have a name?

Does graph shown below from the paper Dissection Graphs of Planar Point Sets by P. Erdos, L. Lovasz, A. Simmons, and E.G. Straus have a name? Does it come from a family of related graphs?
0
votes
0answers
46 views

What's the difference between a 2-sided and 2-sided strip polytan

There are 14 2-sided tetratans and 13 2-sided strip tetratans. The sets are identical, except the square is missing in the strip version. My best guess is that for strips, no vertex can have an edge ...
0
votes
1answer
32 views

Can more than one hamiltonian graph have the same set of hamiltonian paths?

For some pair of non-isomorphic hamiltonian graphs, can there be a chance that it be shown to have the same set of all hamiltonian paths in each graph? we get the set of all hamiltonian paths in each ...
0
votes
1answer
45 views

Using Euler's formula

I have a question related to Euler's formula and whilst I understand the formula I'm not really sure about the question: Let $V_{k}$ be the number of vertices of P from which exactly k edges emanate, ...
2
votes
1answer
87 views

Finite Vertex-Transitive Planar game of Civilization?

If you have played games in the Civilization series, you will have noticed that the Earth is represented in a simplified and profoundly unsatisfying way. It is wrapped around the curve of a cylinder ...
4
votes
1answer
58 views

Points on a plane

I have been assigned this problem and am not sure how to approach it! Please help me figure out what I should do! Let $S$ be a finite set of points in a plane chosen to have the property that for ...
4
votes
1answer
45 views

graph theory, geometry

I have some box with dimensions x,y,z. I put a net around it which includes the top and bottom. The net has unit squares on it. Whats the maximum amount of cuts you can make on the net but still have ...
0
votes
0answers
92 views

How to divide plane with four circles to get Maximum number of region [duplicate]

I started to divide flat plane with one circle to get maximum number of regions and I got 2. Then I tried to do this with two circles And I got 4 different regions. Then I did this with tree circles ...
7
votes
1answer
128 views

“Anti-Gray codes” that maximize the number of bits that change at each step

Let $N$ be a non-negative integer and let $S$ be some ordering of the $2^N$ distinct $N$-tuples of binary digits. We can look at the number of bits that change from each element to the next, and add ...
3
votes
1answer
70 views

small circle inside embedding of complete graph in the plane

On the web, I found this beautiful drawing of the complete graph on 13 vertices: It is on the Geometry Daily tumblr page. A computer scientist drew a more interactive version up to about 40 ...
2
votes
0answers
48 views

Convex polyhedral decomposition of spheres

Is there a decomposition of $S^2$ into $k$ (geodesically) convex polyhedra that are congruent to each other? What about $S^n$ for $n>1$? Remarks: A polyhedron is defined as an area enclosed by a ...
2
votes
1answer
62 views

Equators and meridians on a discrete torus

Consider the 4 × 4 grid graph: Now torify it, i.e. connect its opposing vertices: How can one tell the difference between a “meridian” and an “equator”? The ...
3
votes
1answer
218 views

Star-Shaped polygons

We call a polygon star-shaped if there exists at least one point for which the entire polygon is "visible" from that point. The set of such points we call the kernel of the polygon. The art-gallery ...
1
vote
0answers
49 views

Graphs that “polygonize” a manifold

It's rather easy to conceptualize a covering of the Euclidean plane by a countable set of convex but otherwise arbitrarily sized and shaped polygons (seen as subsets of the plane) without overlaps. It ...
3
votes
0answers
99 views

Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...
1
vote
1answer
108 views

Graph Isomorphisms, Delaunay Triangulation on a sphere, and Kulikowski's Theorem

Suppose I have a collection of $n$ non-collinear points on a sphere, $\left\lbrace P_i\right\rbrace_{i=1}^n $. And I construct a mapping from this collection of points to the Delaunay Triangulation ...
4
votes
2answers
144 views

Can lines connecting nearest neighbors ever cross?

I don't have any background in graph theory so I am sorry if this is a basic question. I want to know if lines connecting nearest neighbors can cross in a few different cases. I have convinced ...
0
votes
1answer
183 views

Affine plane of order 4?

I cannot seem to construct an affine plane of order 4. I have the construction for order 3- but cannot seem to come up with or find the construction for 4 anywhere. Could someone show me a picture of ...
1
vote
1answer
290 views

Calculating distance in a hexagonal grid map

Say I have this map: The first two digits on each hex represent the X axis, the last two digits the Y axis, with 60º between both. How do I calculate the shortest distance between two hexes? E.g. ...
4
votes
1answer
117 views

“Isolated” pieces in figures of triangles

Let us consider a figure of the Euclidean plane comprised of finitely many non-degenerate non-overlapping triangles (i.e., no triangle has a zero area and no two distinct triangles have any inner ...
4
votes
2answers
51 views

How to find bounds on the Euler characteristic

Let $G=(V,E)$ be a connected planar graph. This graph has an Euler characteristic given by $\chi=v-e+f$, where $v$ is the number of vertices, $e$ the number of edges and $f$ the number of faces. I ...
0
votes
2answers
55 views

Can we define the shape of a polygon in the plane using its interior angles?

I know a polygon can be well defined by specifying its edge length. By well defined, I mean the polygon can be unambiguously determined. Loosely speaking, if there are $n$ vertices, $2n-3$ critical ...
2
votes
1answer
211 views

Given an arbitrary number of points, how do you find an equidistant center?

Given an arbitrary set of points on a Cartesian coordinate plane, is there a generalized formula to find the closest point that is equidistant from all the given points? My first guess was finding ...
7
votes
1answer
398 views

Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board. At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
1
vote
3answers
70 views

Finding the number of edges that connect to a single vertex in a dodecahedron

Please note my geometry background is very weak (high school geometry is all I have), so I would appreciate it if someone could explain it in very layman terms how to do this. I am trying to solve ...
2
votes
1answer
93 views

Selecting and Grouping a set of points in a 2D plane

I am currently working on a project that requires to solve the following problem: Let's say that each time a user access a specific resource on the network from his mobile device, a system stores his ...
5
votes
1answer
903 views

Shortest path algorithm used with Google Maps

Maybe posting this question here is wrong, if so I'm sorry and please close this topic. I was wondering which shortest path algorithm is used by Google Maps to find the minimal route between two ...
1
vote
1answer
347 views

Find out the border of a planar figure for given a set of points – 2D case

Original post is edited after getting some suggestions; I am looking for a fast algorithm which is able to detect outer most boundary of a plane for given set of points. Suppose, I have 3D point ...
4
votes
1answer
306 views

Circle packing representation of a given graph

Based on the Circle packing theorem: "For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G." I would like to draw the circle ...
5
votes
1answer
142 views

Origin of a problem in graph theory/planar geometry

Does anyone remember where does the following problem comes from: Let $P_n$ be a set of $n$ points on the plane, and denote by $d$ the minimal distance between any two points of $P_n$ (i.e. ...
18
votes
2answers
398 views

Connecting a $n, n$ point grid

I stumbled across the problem of connecting the points on a $n, n$ grid with a minimal amount of straight lines without lifting the pen. For $n=1, n=2$ it is trivial. For $n=3$ you can find the ...
1
vote
0answers
204 views

Average distance between features in plane of connected points with known average distance

I was doing some thought experiments for a game project, and while considering something related to pathfinding, this problem came into my head. Say we have an infinite plane that is covered with an ...
0
votes
1answer
84 views

Largest uniquely-identifiable subset of regions of space within complete graph $K_n$

Apologies if the title is unclear, I couldn't think of a good way to express what I want. Given the usual 2D representation of the complete graph $K_n$ as a regular $n$-gon with each pair of vertices ...
1
vote
1answer
453 views

Distinct Hamiltonian cycles of the icosahedron and dodecahedron

I am seeking a listing of the distinct Hamiltonian cycles following the edges of the icosahedron and the dodecahedron. By distinct I mean they are not congruent by some symmetry of the icosahedron or ...