All Questions
Tagged with planar-graphs geometry
42
questions
3
votes
0
answers
58
views
Which graphs can be represented as adjacencies in a rectangular subdivision?
The TL;DR version:
Is there a simple characterization of graphs representable by adjacencies of a subdivision of a rectangle into smaller rectangles?
Now the longer version:
I am working on a ...
- 10.5k
1
vote
1
answer
59
views
what is the maximum number of vertices after a 3D planar and regular polygon was truncated by a 3D box?
Let me use a 3D square as an example first. A 3D planar square has four vertices. If this square was truncated by a 3D box, then I can tell that the maximum number of vertices ($NV_{max}$) is eight, ...
- 141
1
vote
1
answer
61
views
Symmetries in regular "floral" circle patterns (seed of life etc.)
Consider $n$ equally sized circles $c_i$ in the plane with their centers $x_i$ in the vertices $v_i$ of a regular $n$-gon and all meeting in the center of that $n$-gon.
Examples:
Fig. 1: circle ...
- 21
2
votes
1
answer
44
views
Prove that the complement of a simple embedded graph $G$ is not embeddable on an orientable surface of genus $g$
Problem: Let $G$ be a simple graph embedded on an orientable surface of genus $g$ with $n$ vertices. For which values of $n$ (depending on $g$ ) can we prove that the complement of $G$ is not ...
- 1,238
1
vote
1
answer
54
views
Do all planar rigid graphs contain a triangle?
If one looks at rigid rod and joint linkages (such as the Laman graphs) one instantly notices a similarity between them, which is that all of them either contain $K_3$ or something which contains $K_{...
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
1
vote
1
answer
54
views
Degenerate Schläfli symbols involving 1
I understand that Schläfli symbols with integral elements $\{p,q\}$ both greater than or equal to $2$ represent planar graphs (multigraphs if $p$ is $2$), and these graphs, if finite, represent ...
- 13
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
0
votes
0
answers
60
views
What is "the plane" in graph theory?
I have learnt that a planar graph is a graph which can be drawn on the plane without any of its edges crossing. What exactly is "the plane"? In plane geometry, we define a plane to be a flat ...
- 3,019
3
votes
1
answer
71
views
Find segment x on the secant circles below
In the figure determine $'x'$ , knowing that $PM=MQ=4$ and $O$ and $O'$ are centers.(S:$x=4$)
I try:
$\triangle OQH \sim \triangle OAP \implies \dfrac{HO}{OP} = \dfrac{HQ}{AP} = \dfrac{8+OP}{AO}$
$\...
- 7,031
2
votes
0
answers
64
views
Does a quadrangulation with minimum degree $3$ contain either a $(3,3)$ edge or a $(3,4)$ edge$?$
A simple graph $G$ is a quadrangulation of the plane if it can be embedded in
the plane in such a way that all faces are quadrangles. We say an edge $e=(uv)$ is an $(a,b)$-edge if the degrees of the ...
- 2,474
2
votes
1
answer
94
views
Argue that in a planar graph on n nodes there is an independent set of at least n/8 nodes, each of degree at most 11.
I am having troubles with this question. Seems non-trivial as I see it. The tightest lower-bound I could reach was "at least n/12" number of nodes in the independent set, with the assumption ...
- 63
3
votes
1
answer
156
views
Analogous formula for finding “non-planar graphs” using defined faces instead of edges in $\Bbb R^3$?
Given a graph, along with a set describing which edges are connected to form faces, how could we determine whether it is embeddable in 3D Euclidean space, a.k.a $\Bbb R^3$? What formula applies here?
...
- 172