Wondering if it is possible to construct a planar graph from any non-planar graph by adding vertices (or splitting edges arbitrarily), and if so, if there is any technique to it. Wondering if there is any study of how to generate specific planar shapes and such out of arbitrary graphs. If not, why not. I'm thinking along the lines of just doing this: adding points wherever the edges overlap. But then how to create shapes. Not sure if there is any math done on this already.
2026-03-25 01:25:57.1774401957
Obtaining a planar graph from a non-planar graph through vertex addition
1.1k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in GRAPH-THEORY
- characterisation of $2$-connected graphs with no even cycles
- Explanation for the static degree sort algorithm of Deo et al.
- A certain partition of 28
- decomposing a graph in connected components
- Is it true that if a graph is bipartite iff it is class 1 (edge-coloring)?
- Fake induction, can't find flaw, every graph with zero edges is connected
- Triangle-free graph where every pair of nonadjacent vertices has exactly two common neighbors
- Inequality on degrees implies perfect matching
- Proving that no two teams in a tournament win same number of games
- Proving that we can divide a graph to two graphs which induced subgraph is connected on vertices of each one
Related Questions in POLYTOPES
- Is every finite descending sequence in [0,1] in convex hull of certain points?
- Can we really move disks around a compact surface like this?
- The permutations of (1,1,0,0), (-1,1,0,0), (-1,-1,0,0) are vertices of a polytope.
- Smoothness of a polytope
- Schlegel diagram and d-diagram
- How to find the "interior boundary" for a set of points?
- Simplicial polytope in $\mathbb{R}^n$ with $n+2$ vertices
- What are some examples of 2-polytope/3-polytope that are not simple?
- Contraction of oriented matroid as related to polytope?
- Finding the vertices of linear image of the $n$-simplex
Related Questions in PLANAR-GRAPHS
- max planarity and triangulation
- How to find a minimal planar covering of a graph
- Complete bipartite planar graphs
- Is graph Planar?
- Kuratowski's theorem on Planar graphs
- Graph Theory: Degree of regions in a planar graph
- On the Hex/Nash connection game theorem
- Graph Theory: There is only one planar graph with all vertices of degree 4 and 10 regions
- Intersection of circles and regions
- Which of these graphs is planar?
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?


It depends on what you mean by "adding vertices."
The usual meaning is to place a new point which is then connected by zero or more edges to existing points. In that case, it is almost obvious that you cannot get a planar graph from a non-planar graph, because there will be a subgraph of the new graph (namely the original non-planar graph) that cannot be expressed in a plane.
But if "adding a point" can mean adding a point along an edge, breaking that edge and requiring the corresponding two edges to connect to the new point (along perhaps with other edges) then yes, you could turn a non-planar graph into a planar graph.
For example, take a 5-clique, which is non-planar. Choose an edge, wlog edge $AB$. Remove that edge and replace it with two edges connecting a sixth point $F$ (so that the new graph has $AF$ and $FB$ in place of $AB$). This new graph is planar.
I believe determining whether a given graph is planar, knowing only its matrix of edges, is a hard problem.
I believe I need to explain my example in more detail:
In a plane, picture geometrically points $$\{ A = (0,1); B = (0, -1); C = (1,0); D = (-1,0); E = (0,0) \}$$ and edges depicted by lines $AC$, $AD$, $AE$, $BC$, $BD$, $BE$, $CE$, $DE$, plus an edge between $A$ and $B$ drawn as an arc within the same plane, and one last edge between $C$ and $D$ (making this $K_5$) drawn as a curve going slightly out of the plane, going from $C$ around the outside of $A$, just over the $AB$ arc, and coming back down near $D$.
Now break (as the OP is trying to allow in his problem) arc $AB$ into arcs $AF$ and $FB$, both still using the same drawn curve (and in the plane). Then push arc $CD$ dwon into the plane such that it would cross arc $AB$ at $F$, and break up $CD$ into $CF$ and $FD$. The resulting graph of six vertices is now planar (indeed, the planar edge set has been exhibited by construction). It is not, or course a 6-clique, nor does it contain $K_5$ as a subgraph, but this does meet the OP's desire for "flattening" a graph.