All Questions
Tagged with planar-graphs co.combinatorics
38 questions
36
votes
21
answers
6k
views
Generalizations of Planar Graphs
This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
- 24.7k
14
votes
1
answer
2k
views
Is every graph the center of some other graph?
The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...
- 151k
14
votes
2
answers
1k
views
Is there easy proof for triangle-free two-coloring of planar graphs?
By merging two-two color classes, the Four Color Theorem implies that every planar graph can be two-colored such that each color class induces a triangle-free graph.
Is there a simpler proof for this ...
- 18.7k
11
votes
3
answers
675
views
Is a distributive lattice planar iff it admits no B3 sublattice?
A finite lattice is planar if it admits a Hasse diagram which is a planar graph (we want the Hasse diagram to be represented in the plane so that the $y$-coordinate of each element respects the order)...
10
votes
1
answer
369
views
Orientations of Planar Graphs
Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient
the edges of $G$ such that for each vertex $v$, there are no
three ...
- 175
9
votes
2
answers
576
views
Do planar graphs have an acyclic two-coloring?
A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest.
Does every planar graph have an acyclic two-coloring?
An affirmative ...
- 18.7k
8
votes
0
answers
404
views
Parity of oriented rooted trees
Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...
user174224
7
votes
2
answers
252
views
There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?
Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
- 1,190
7
votes
1
answer
413
views
Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?
$\DeclareMathOperator\cl{cl}$The cyclic edge connectivity $\cl(G)$ is the size of a smallest cyclic edge cut, i.e., a smallest edge cut $F$ such that $G-F$ has two connected components, each of which ...
- 1,851
7
votes
1
answer
2k
views
Why $K_5$ and $K_{3,3}$?
Most people will have already guessed that this is about Kuratowski's theorem.
The theorem states that every non-planar graph must contain a complete graph $K_5$ with five vertices or a complete ...
- 857
7
votes
2
answers
1k
views
Planar layouts of bipartite graphs
Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.
It would be very convenient if there was a ...
- 4,462
6
votes
2
answers
717
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 557
6
votes
1
answer
565
views
Does every $4$-connected nonplanar graph contain a $K_5$-minor?
By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$.
But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not ...
- 341
6
votes
1
answer
290
views
Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4
Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?
- 1,190
6
votes
3
answers
526
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 1,851
5
votes
1
answer
479
views
Can all crossings in a graph be moved to one point?
Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
- 4,829
5
votes
2
answers
553
views
"Locally Nonplanar" graph
A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...
- 1,034
5
votes
0
answers
134
views
Equitable 4-colorings of planar triangulations
In an
equitable coloring
of a graph $G$, the number of vertices in each color class differ
by at most $1$.
For example, left below is not an equitable coloring, while the
right graph is equitably ...
- 151k
4
votes
1
answer
450
views
Implementation of Koebe–Andreev–Thurston circle packing?
The circle packing theorem (Koebe–Andreev–Thurston theorem) claims for a planar graph, we can pack disjoint circles, such that: the circles correspond to vertices and the disks are tangent if the ...
- 1,465
4
votes
0
answers
65
views
is a 4-connected planar graph still Hamiltonian after removing an edge?
We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
- 1,851
4
votes
0
answers
281
views
Reference for results about planar graphs
A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...
- 2,339
3
votes
2
answers
282
views
Planar graph of high valence
A classic result in graph theory tells us that any planar graph must have at least one vertex with valence no bigger than 5. On the other hand, there exist examples of planar graphs that are 5-regular ...
- 540
3
votes
1
answer
158
views
Sharp upper bound of the number of edges for graphs of thickness two
A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
- 1,065
3
votes
1
answer
359
views
Is there a way to generate all 5-connected 5-regular planar graphs?
My question was partly inspired by the question linked below.
There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?
I see a wonderful construction of Adam P. Goucher,...
- 1,851
3
votes
1
answer
377
views
Minimum planar bipartite graph to cover all perfect matching count
Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.9k
3
votes
2
answers
184
views
Does any long path in a planar graph contain one of O(n) k-tuple of vertices?
My question is a bit related to both the container method and shallow cell complexity.
Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!)...
- 18.7k
3
votes
0
answers
98
views
Number of planar bipartite graphs
How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?
- 13.9k
3
votes
0
answers
136
views
Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?
In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1.
Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
- 1,851
3
votes
0
answers
166
views
Known bounds of the maximum cut of planar graphs
The well-known max cut problem asks for a largest cut of a graph $G$. A cut
of maximal size clearly corresponds to a bipartite subgraph of maximal size.
After my inquiry, in planar graphs, the maximum-...
- 1,851
2
votes
1
answer
170
views
Is there an algorithm to generate non-isomorphic Halin graphs?
A Halin graph is a graph constructed by embedding a tree with no vertex of degree
two in the plane and then adding a cycle to join the tree’s leaves.
We found a list of the number of Halin graphs ...
- 1,851
2
votes
0
answers
48
views
On planar graphs with specific spanning tree count and poly number of vertices
Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
- 13.9k
2
votes
0
answers
235
views
Injection of Catalan objects into 3-connected planar graphs
Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon.
Let $P_n$ be the number of three-connected planar ...
- 5,792
2
votes
0
answers
91
views
Blind construction of planar graph with additive spanning tree count
Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
- 13.9k
2
votes
0
answers
190
views
The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$
Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...
- 237
1
vote
1
answer
114
views
Removing a face from 4-connected planar graph
After removing a face (vertices along with edges) of a 4-connected planar graph, is the remaining graph 4-connected? Alternatively under what conditions is this true?
- 129
1
vote
1
answer
173
views
Who introduced the concept of beyond planar graphs?
The concept of planar graphs seems to be standard (I'm also not sure who first used this term), and recently, beyond planar graphs attract a lot of interest in the field of graph drawing. I know that ...
- 1,851
0
votes
3
answers
133
views
Even regular planar graphs without 2-cycles
Related to another question I asked, some questions came up, the most important is the following:
Are there any 4-regular planar graphs without 2-cycles + 3-cycles?
Could someone draw an example if ...
- 183
0
votes
0
answers
133
views
is there an example in planar graph that using probabilistic methods
The probabilistic method is a technique for proving the
existence of an object with certain properties by showing that
a random object chosen from an appropriate probability
distribution has the ...
- 1,851