Mathematics Stack Exchange
Mathematics Stack Exchange

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].

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 and .

A finite graph $G$ is planar if and only if no minor of $G$ is the complete graph $K_5$, or the complete bipartite graph $K_{3,3}$ (Wagner's Theorem).

1057 questions
4
votes
0 answers

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 each state and connect it to the three common…
Richard Stanley
  • 381
2
votes
1 answer

Planar Graph Embedding with fixed vertex positions

Given a planar graph, and an arbitrary prescription for its vertex positions in in the plane. Can you always draw the edges of the graph without crossings (not straight segments, of course) for any given vertex positions? I guess it is a bit like…
Amir Vaxman
  • 415
2
votes
1 answer

Is the maximum degree of a planar graph 5?

I'm trying to study (by myself) planar graphs. On the book I'm reading, I came across this sentence about the 5-coloring problem that I really don't understand: Lemma 5.8.15. Every planar graph has a vertex of degree at most five. Proof. By…
Aurasphere
  • 131
1
vote
1 answer

Number of Vertices of a connect planer graph with 100 edges

Assume $G$ is a connected planar graph with 100 edges. While the edges can be split into two sets, $S_1$ and $S_2$ such that $|S_1|=60$ and $|S_2|=40$. Given that for all $e$ in $S_1$, the face on one side of $e$ has 3 edges, and the face on the…
Vincent
  • 13
1
vote
0 answers

How to draw planar graphs of that satisfy Euler's formula

The full question is: In each case, give the values of $r$, $e$, or $v$ assuming that the graph is planar. Then draw a connected planar graph with the property, if possible. The values I was given were 6 vertices all of degree 4 and another…
Shawn Li
  • 11
0
votes
1 answer

Determining Planar Graphs

Take a hexagon and add the three longest diagonals. IS the graph obtained this way planar? I'm able to draw the graph very easily. But I don't really understand how to determine what graphs are planar and which aren't.
jerry2144
  • 643
0
votes
1 answer

Suppose G is an unconnected planar graph, with v nodes, e edges, and f faces, where v ≥ 3.

This is a corollary of Euler's formula. I know the proof for connected planar graphs but I have to prove it for unconnected planar graphs. Suppose $G$ is a connected planar graph, with $v$ nodes, $e$ edges, and $f$ faces, where $v \geq 3$. Then…
Giorgia
  • 7
0
votes
2 answers

Let G= (V,E) be an undirected connected loop-free graph.Prove that...

Let G = (V,E) be an undirected connected loop-free graph. Suppose further that G is planar and determines 53 regions. If for some planar embedding of G, each regions has at least 5 edges in its boundary, prove that $|v| \ge 82$.
a1bcdef
  • 2,265
0
votes
1 answer

Planar graph minimum 3 verticies of degree leq 5

Let G be a planar graph with at least 3 verticies. Prove that G contains at least 3 verticies whose degree is $\leq 5$. What i have tried to do: Lets suposse that there exist a planar graph with at least 3 verticies that has only at most 2…
user2184057
  • 251
  • 2
  • 9
0
votes
0 answers

planar 4 regular graph

if a planar 4 regular graph is only made of 3 and 4 corners and let´s say it has "s" a defined number of 4 corners then how van i find the number of 3 corners using the euler.P.formula . I saw online that it is the same number of 4 corners but with…
sl243
  • 11
0
votes
2 answers

Prove this graph is not planar.

I need to show this graph is not planar. I've attempted to find a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ but haven't been successful yet.
Carlos Andres Henao Acevedo
  • 475
0
votes
0 answers

Proving K4,6 is non-planar

I'm trying to prove the graph K4,6 is non planar. Here's what I have so far: Let's assume the graph is planar and hence it satisfies Euler's relationship: R(regions) + N(nodes)=A(arcs)+2. We know N=4+6=10 and A=4x6=24 hence using the above equation…
LaurenceMeister
  • 11
0
votes
0 answers

How to measure the 'skew-ness' of a set of vertices?

Let's say we have, on a 2d axis, four vertices that form a rectangle. A rectangle is, from one perspective, a stretched out square... so you could say a rectangle is more 'skewed' than a square. Is it possible to measure this 'skewness'? I think of…
LangerNZ
  • 125
0
votes
0 answers

Problem with definition of planar graphs.

Is a graph with only vertices and no edges counted as a planar graph? And is a graph with only one edge also considered as a planar graph.
Zirconia
  • 11
0
votes
1 answer

Why are points considered to be zero dimensional?

Aside This is a silly observation born out of my own curiosity. I'd love some perspective from more mathematically minded folks. Please try to evaluate my reasoning, and expand on which assumptions are incorrect or misguided. General question Why…
efreezy
  • 119
1
2