All Questions
Tagged with graph-theory planar-graphs
35 questions with no upvoted or accepted answers
13
votes
0
answers
212
views
Does there exist 2-planar graph with chromatic number 8 or 9 or 10
A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
- 1,190
9
votes
0
answers
194
views
Partitioning the vertices of a graph into induced trees
I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree.
In particular I am ...
- 12.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
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
0
answers
67
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
282
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
4
votes
0
answers
144
views
Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?
Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.
If not, what is the smallest n so that ...
- 111
4
votes
0
answers
108
views
Reference on generalization of plane graph duality between bonds and simple cycles
Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...
- 1,462
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
3
votes
0
answers
222
views
Reconstructing plane graphs from degree- and face-sequences
Let $G$ be a plane $3$-connected graph; so it partitions the plane
into regions bounded by faces.
Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$,
and $\mathrm{deg}_f$ be the sequence of ...
- 151k
2
votes
0
answers
86
views
Does there exist a 5-connected planar graph that is perfect?
I asked this question on math stack, but didn't get any response, so I ask it here.
In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ ...
- 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
75
views
Is the chromatic number of every 7-connected 1-planar graph at most 5?
1-planar graphs were first studied by Ringel (1965), who showed that they can be colored with at most seven colors. Later, the precise number of colors needed to color these graphs, in the worst case, ...
- 1,851
2
votes
0
answers
63
views
What is the range of connectivity for maximal IC-planar graphs?
A graph is IC-planar if it admits a drawing in the plane with
at most one crossing per edge and such that two pairs of crossing edges
share no common end vertex. A graph $G$ is maximal in a graph ...
- 1,851
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,822
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
106
views
Decomposing a planar graph
Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
- 3,153
2
votes
0
answers
48
views
Planarity of a subgraph
Given a complete symmetric graph $G(V,E)$ with real-valued edgeweights and assume that every induced $k_4$ that is induced by a quadruplet from $v$'s vertices has a unique perfect matching of maximal ...
- 13.2k
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
0
answers
97
views
Problem related to crossing number
Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$.
Denote $\delta(v)$ the set of edges with one ...
- 111
1
vote
0
answers
77
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of ...
- 111
1
vote
0
answers
52
views
Mac Lane-like condition for intrinsically linked graphs?
If any embedding of your graph in 3-space has two cycles that are linked, then your graph is intrinsically linked (such as the Petersen graph). These graphs generalise non-planar graphs since for ...
1
vote
0
answers
337
views
What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?
Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph?
Update ...
- 1,826
1
vote
0
answers
78
views
Planar graphs with perfect matching count in linear time?
We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication.
We know that permanent of $O(n)$ vertex planar ...
- 13.9k
1
vote
0
answers
170
views
Smallest planar graph with two non-homoemorphic plane embeddings?
Apologies for asking a question which probably has a well-known answer:
What is the smallest (not necessarily simple) planar graph with two non-homeomorphic embeddings into the plane?
I am ...
- 241
1
vote
0
answers
149
views
Determine sub-polygon from line segments with known member connectivity
Test Polygon:
Consider the following polygon as attached. Let the known parameter be as follows:
•Member to member connectivity, i.e. it is known that A – B, X – E, F – B, etc. for all the members.
•...
- 19
1
vote
0
answers
221
views
A connection between nonplanar complete graphs and the alternating groups?
I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...
- 1,197
0
votes
0
answers
52
views
Are there 4-connected planar non-hamilton multi-graphs?
Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
- 1,851
0
votes
0
answers
81
views
Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?
A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.
A minor of graph G is a graph obtained from G by ...
- 1,190
0
votes
0
answers
35
views
Arbitrarily high degree planar covers?
All the graphs I want to discuss are finite, simple, and connected. A graph $G_1$ covers another graph $G_2$ if there is a surjective map $\pi : V(G_1) \to V(G_2)$ that sends edges to edges and such ...
- 1,075
0
votes
0
answers
233
views
I don’t understand the two ISOMORPHISM embedding definitions of planar graph in plantri software
The plantri (see http://users.cecs.anu.edu.au/~bdm/plantri/) is a program that generates certain types of graphs that are
imbedded on the sphere. Exactly one member of each isomorphism class is output....
- 1,851
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
0
votes
0
answers
367
views
crossing number and thickness of a simple graph $G$
Crossing number$($cr$)$: The crossing number of a simple graph is the minimum number of crossings that can occur when this graph is drawn in the plane where no three arcs representing edges are ...
- 101