Questions tagged [planar-graphs]
A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane such that the edges only intersect at vertices. Consider tagging with [tag:combinatorics] and [tag:graph-theory]. For embeddings into higher-genus spaces, use [tag:graph-embeddings].
240
questions with no upvoted or accepted answers
18
votes
0
answers
382
views
Algorithms for "pleasing" drawings of planar graphs, possibly on sphere
What algorithms exist to draw planar graphs without edge crossings in a way that they are easy to interpret by humans?
There are multiple algorithms that can handle any planar graph, such as Schnyder'...
- 1,127
11
votes
0
answers
302
views
Can every tree with total length $2$ be covered by a semi-disc of radius $1$?
Can every tree with total length $2$ be covered by a semi-disc of radius $1$?
If the tree is actually a curve, or the convex hull of the tree is a triangle, I know this is correct after some attempts. ...
- 954
11
votes
0
answers
488
views
Parity on the number of rooted trees
Suppose we have a planar graph with vertices $v_0, \ldots, v_n$, where $n$ is even such that there exist a checkerboard coloring of the regions in the complement such that the black regions are $n$ (...
user895424
8
votes
0
answers
146
views
On a lemma for planar graphs
Throughout, let $G$ be a planar graph with $n$ vertices, $e$ edges and $f$ faces. Additionally, let $n_k$ be the number of vertices of degree $k$ and $f_k$ be the number of faces with $k$ edges.
I ...
- 903
6
votes
0
answers
262
views
How to draw a planar-embedded graph in a visually pleasing way
I have a graph with two types of vertices: "boundary" vertices have degree 1, and "interior" vertices have degree 4. I've computed a planar embedding of the graph, i.e. around each ...
- 9,684
6
votes
0
answers
230
views
Can identical rings intersect in any combinations in 3d space?
For every undirected graph G, with nodes $a_1,...,a_n$. Can we find n circles/rings of fixed radius, $c_1,...,c_n$ in 3 dimensions such that there exists an edge between $a_i$ and $a_j$ if and only if ...
- 136
6
votes
1
answer
3k
views
When counting faces in a planar graph - when is each edge counted twice?
So I'm confused even though this is supposed to be simple:
From what I understand, in a planar graph, if we count the edges of each face, we should get $\sum F_t \le 2|E|$ because an edge can ...
- 389
5
votes
0
answers
190
views
The upper bound on the number of four cycles of 3-connected quadrangulation graphs.
Recently I was thinking about a question:
what is the upper bound on the number of four cycles for 3-connected quadrangulation graphs with $n$ vertices?
I use the plantri software, and propose the ...
- 2,474
5
votes
1
answer
130
views
How many vertices does a planar graph need to have a complete $k$-colouring?
A proper colouring $V(G) \to \{1,...,k\}$ of a graph $G$ is complete if every distinct pair of colours is connected by an edge. What is the least $n_k$ such that there exists a planar graph on $n_k$ ...
- 1,535
5
votes
0
answers
256
views
Chromatic Number Range of Dual Graphs?
A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$.
Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$.
Using $\chi$ to denote ...
- 553
5
votes
0
answers
200
views
Alexander duality and simplicial complexes
A consequence of Alexander duality is the fact that an $n$-dimensional simplicial complex $K$ embedded in $\mathbb{R}^{n+1}$ separates $\mathbb{R}^{n+1}$ into $\beta_n + 1$ connected components where $...
- 732
5
votes
0
answers
139
views
Isometrically embed $K$-gon into $\mathbb{R}^N$
In this post, the regular $K$-gon is the metric space $M = \{1,\dots,K\}$ such that, for $k,l \in M$,
$$d(k,l) := \begin{cases}
|k-l|, & |k-l| \leq K/2, \\
K-|k-l|, & |k-l| > K/2.
\end{...
- 535
4
votes
0
answers
99
views
What is the name of this graph?
By plantri, we know that the following graph is the unique planar graph with 15 vertices of minimum degree 5. I add the graph in The House of Graphs (Graph 49406).
But I do not know if it has a name....
- 2,474
4
votes
0
answers
91
views
Where can I find a proof of the 4 color theorem
Where can I find a reasonably understandable proof on how to reduce to a finite number of configurations?
Also any videos on this would also be appreciated
- 468
4
votes
0
answers
81
views
Three points in common to three states of the USA
Many years ago I encountered the question: what three states of the USA have three points in common to all three of them? At first this seems impossible since we can put a point in the interior of ...
- 391