All Questions
Tagged with planar-graphs plane-geometry
13
questions
0
votes
0
answers
29
views
Percentage of acute triangles [duplicate]
There are 100 dots in a surface. A math lover draw all the triangles possible such that the vertices of the triangle will be those dots. X is the maximum percentage of acute triangles in those ...
- 11
0
votes
0
answers
45
views
Can a vertex lie on an edge in a planar graph?
I am wondering if a vertex can lie on an edge in a planar graph- I am not sure if an edge of this vertex is regarded as crossing the edge on which the vertex lies. I have two questions here:
Is the ...
- 3,019
0
votes
0
answers
34
views
Are the edges of a planar graph part of its faces? (Graph Theory)
The definition of face I have learned for planar graphs is "a region where any 2 points in it not on $G$ can be connected by a line which doesn't intersect any of the edges of $G$". I am ...
- 3,019
1
vote
1
answer
68
views
How is the face for a tree graph bounded by any sides at all? (Graph theory) [closed]
I have learnt that every face in a planar graph has sides, and that sides are edges which bound the face clockwise. I am very confused about a few things regarding sides:
I am not seeing how the ...
- 3,019
2
votes
0
answers
392
views
Prove that $2V - 4 = F$ for maximal planar graphs.
A beautiful proof of the Euler's characteristic of planar graphs goes as follows:
Let $G$ be a connected planar graph and $\chi(G):=V-E+F$. Add as much edges as possible to $G$ (but no vertices!) ...
- 3,881
0
votes
1
answer
213
views
Meaning of Equation of a line
What do we mean by "equation of a line"? How would it be defined? I know its form but what is it exactly?
2
votes
1
answer
97
views
Joining faces in planar graph
Let $G=(\{1,\ldots,n\},E)$ be a conncected graph which is planar in the embedding where the vertices $1,\ldots,n$ are placed equidistantly on the circle and all edges are drawn as straight lines.
This ...
- 2,702
1
vote
0
answers
40
views
Finding Z value at specified X and Y value of Flat Plane
It's been a while since I did any work with planes and I'm having trouble figuring out where to start to find these answers or the best way to explain it. I currently have a line that moves through (0,...
- 11
8
votes
1
answer
1k
views
How many simple polygons can be made with n points?
You have n points which you can arrange in an infinite 2-D space. What is the maximum number of simple n-sided polygons (i.e. where none of the line segments intersect) which you can create from any ...
- 243
2
votes
1
answer
58
views
The number of boundaries among $n$ states?
This question inspires another:
With four states in proximity to each other one often sees five boundaries between states; for example:
$$
\begin{array}{rc}
1 &\text{New York}/\text{Vermont} \\
2 ...
1
vote
1
answer
25
views
Can planar graphs be chained?
Let $G$ be a graph whose vertex set is described as the union of three disjoint sets $V = V_1 \cup V_2 \cup V_3$, and such that there are no edges between $V_1$ and $V_3$. Assuming the subgraphs ...
- 845
1
vote
1
answer
141
views
Separating a planar graph into two components containing shortest paths
Let $G$ be a planar graph containing more than 5 vertices (the choice of '5' is arbitrary, and a bigger minimum vertex number will do just fine). Is it always possible to find a vertex cut $S$ of $G$ ...
- 845
0
votes
1
answer
1k
views
Formula to find an angle of point on a coordinate plane
Given a plane and an arbitrary (x,y) point, is there a succinct formula to find the angle of that point against the positive y-axis? For example, pictured below the green point is 0 degrees, blue 45 ...
- 339