Questions tagged [planar-graphs]
graphs that can be embedded into the plane, i.e. that can be drawn without crossings between the lines representing edges.
96 questions
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
1
answer
95
views
Dipping into sets of parallel edges in graph drawings
Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
- 111
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
1
answer
112
views
Completing a tree to a 2-connected outerplanar graph
Let $T$ be a given (finite) tree.
Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?
Question 2: If the answer to Question #1 is negative, can ...
- 6,962
2
votes
1
answer
138
views
Two ears polygon in a maximal planar hamiltonian graph
Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
- 35
2
votes
1
answer
200
views
Two from cubic subgraph hardness
The Problem
For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3.
The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
2
votes
0
answers
85
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
73
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,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
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
2
votes
0
answers
182
views
Graphs determined by monohedral, edge-to-edge tilings of the plane
Let $\cal T$ be a monohedral, edge-to-edge tiling of the plane, with prototile $T$ a simple polygon, and with one edge $e^*$ of $T$ distinguished. Associate a graph $G=G_{\cal T}$ with $\cal T$ as ...
- 151k
1
vote
1
answer
159
views
When is an ordering of edges in a graph a planar embedding?
Is there a criterion which decides whether a given rotation system for a graph determines a planar embedding? That is, a lemma of the form:
A graph G = (V, E) is planar if and only if there exists ...
- 203
1
vote
1
answer
91
views
Generating 12-vertex plane graphs with 2 faces of degree 3 and all other faces of degree 4
My question may be similar to generating-21-vertex-4-regular-plane-graphs-with-8-faces-of-degree-3-and-15-face., but it has differences. The plane graphs I desire (without needing regularity) have ...
- 1,851
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
160
views
Can Tutte embedding be guaranteed that each face is convex?
In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a ...
- 1,851
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
1
vote
1
answer
295
views
Confused about the definition of convex drawing of plane graph
When I looked up the definition of convex drawing of planar graph, my confusion mainly focused on the outer face.
The following definition of convex drawing is from Wikipedia.
In graph drawing, a ...
- 1,851
1
vote
1
answer
96
views
Cholesky factorization of planar graphs
Suppose the sparsity pattern of $A \in \mathbb{R}^{N \times N}$ is a planar graph. Can I use this to bound the complexity of solving
$$
Ax = b
$$
?
In particular, I was hoping to use the planar ...
- 561
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
69
views
On perfect matchings on planar graphs - is there a linear time deterministic algorithm?
The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree.
MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
- 13.9k
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
67
views
Why are trivalent/cubic graphs 'generic' in surfaces?
I've seen some statements that trivalent graphs in a surface are 'generic'. See for example the Wiki entry on cubic graphs.
I'm wondering how this could be rephrased. Here are some (somewhat imprecise)...
- 545
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
1
answer
377
views
How to prove that there does not exist any plane isotopy from the logarithmic spiral onto the real line? [closed]
Questions.
EDIT: readers please note that while this question arose in research, the OP was so hung-up on a question concerning infinite planar graphs that a strong a-forteriori-reason, kindly ...
- 6,051
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
91
views
"Constrained" Moser's Trick
I wish to know if there is a sort of "constrained Moser Trick". Suppose we have a planar grap $G \subseteq \mathbb{R}^2$, with $(0,0)$ as a vertex. Suppose to have some volume form $\omega = ...
- 1
0
votes
0
answers
26
views
Diffeomorphism of graph with conditions on volume from
I have the following situation: I have a graph $G$ embedded into $\mathbb{R}^2$, with $(0,0)$ a vertex, and I have a diffeomorphism $g$ of the plane. Let's call $G' = g(G)$ the new graph.
I suppose ...
- 1
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
1
answer
201
views
Is graph's planar embedding unique if each block of one planar graph is 3-connected?
A planar graph is one which has a plane embedding. Two drawings are topologically isomorphic if one can be continuously deformed into the other. If we wrap a drawing onto a sphere, and then off again, ...
- 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