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

1
vote
1answer
33 views

Graph planarity definability clarification in literature?

Here it says planarity is definable in first order. http://jgaa.info/accepted/recent/Brandenburg.pdf Here it says planarity testing of graphs is not a first order property. Refer https://simons....
0
votes
1answer
20 views

Planar Eulerian graph

Let G be a planar Eulerian graph. Consider some planar drawing of G. Show that there exists a closed Eulerian tour that never crosses itself in the considered drawing (it may touch itself at vertices ...
0
votes
1answer
44 views

Finding if a subgraph of a minimal non-planar graph is a maximal planar graph

Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal ...
0
votes
1answer
13 views

Outerplanar Graphs with |V| = 2

I am currently working on an assignment for my discrete mathematics lecture. We are currently looking at outerplanar graphs and I am supposed to proof the following. Let G = (V,E) be a outerplanar ...
2
votes
2answers
38 views

How to approach the proof of this formula for triangulations.

I am currently working on an assignment for my discrete mathematics lecture. It is specifically about graphs which are triangulations and have a minimum degree of 3. Triangulation specifically means ...
0
votes
1answer
23 views

If $G$ cubic planar graph with faces only $C_5$ and $C_6$, then $G$ has $12$ pentagons and $0$ hexagons

I want to prove the questions in the title: If $G$ is a connected cubic planar graph composed of only pentagons and hexagons, then it has $12$ pentagons and $0$ hexagons. I was able to show it has $...
1
vote
1answer
27 views

Prove that maximal outerplanar graphs are not bipartite

I am trying to prove that a maximal outerplanar graph $G$ with $n \ge 3$ vertices cannot be bipartite. Intuitively, I think that all the inner faces will be triangles, thus forming odd length cycles, ...
4
votes
3answers
1k views

How can this planar map be coloured using $4$ colours?

I'm working on an algorithm to colour a map drawn in an editor using 4 colours, as a visual demonstration of the four colour theorem. However, my (imperfect) algorithm was able to colour all maps ...
0
votes
0answers
39 views

the maximum number of pairs of K5 subgraphs in an n-planarizable graph

I am having a question in an Assignment at my college: How can i find the maximum number of pairs of node-disjoint-copies of 5-complete (sub-) graphes (K5) which are included in an 5-planarisable ...
2
votes
2answers
70 views

Minimum number of colors to paint a map

Given a planar graph such that all its vertices are of degree 4, find the minimum number of colors needed to paint the map. I've used the Euler formula for graphs $$v-e+f=2$$ where $$v$$ is the ...
0
votes
1answer
17 views

Find a path in oriented graph with cost divisible by N

Let's have a graph evaluated by integers, a number $N$, a stating node $S$ and a goal node $G$. The graph is a square mesh and all edges are oriented rightwards or downwards. Find a path form $S$ to $...
1
vote
1answer
28 views

planar graph of Submultiples [duplicate]

There is Graph which is connected with Submultiples. (I am sorry but I don't know what this is called.) For example, 10-node Graph has 10 nodes, 18 edges. node 1 connect all the other nodes. node 2 ...
2
votes
1answer
29 views

Graph Theory Question About Paintings On Walls.

I am faced with the following question for my undergraduate Graph Theory class: Suppose a person is standing in a room which has a painting on each of its walls. Prove that if the room has at most ...
0
votes
0answers
78 views

Finding the number of edges of a triangulation of a polygon on n vertices

I am faced with the following question: A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon and all of whose other faces are triangles. How many edges does a ...
3
votes
1answer
61 views

Can you prove $K_{3,3}$ is not planar without the Jordan Curve Theorem?

The non-planarity of $K_{3,3}$ is well know and e.g. shown here: 3 Utilities | 3 Houses puzzle? However, it is pointed out that the given proofs all use the Jordan Curve Theorem in one form or ...
0
votes
1answer
40 views

Confusion over order of transformations of graphs

I did a search on the order of transformations applied to graphs, and mostly found the following, e.g. in this post. Given a function $f$ always perform transformations $$Af(Bx+C)+D$$ in the order $...
7
votes
1answer
147 views

Maximum Regions Vees Can Divide a Circle

The Circle Division by Lines problem (link) asks into how many regions, at most, one can divide a circle (or: the plane) with $n$ chords (or: lines). I am wondering about a similar question, but for ...
3
votes
2answers
88 views

Planar graph with 9 vertices and 3 components property

I have been preparing for graph theory exams and found a statement that: Let $G$ be a planar graph with 9 vertices and 3 components. Then complement of graph $G$ is not a planar graph. How can we ...
0
votes
2answers
22 views

Is this specific example of a graph having 10 vertices and 25 edges planar or non-planar?

Let $N = \{1, 2, 3, 4, 5\}$ Let $G$ be an un-directed graph defined as follows: Let $VERTS(G)$ denote the vertex set of $G$. $N$ subset of $VERTS(G)$ For all $k$ ∈ $N$, $N/\{k\}$ ∈ $VERTS(G)$ ...
0
votes
0answers
12 views

Connectivity property between k and k+1 connectivity

Following an older question of mine Maximum connected components after removing 2 vertices. It turns out that for the family of graphs I talk about, we can have 1,2 or 3 connected components after the ...
0
votes
0answers
19 views

Diestel, Thm. 4.3.1, graph-theoretical isomorphism implie combinatorial?

In the book Graph Theory of R. Diestel, Theorem 4.3.1(i) says that Every graph-theoretical isomorphism between two plane graphs is combinatorial. Its extension to a face bijection is unique if ...
2
votes
1answer
23 views

Proof that if convex polyhedron doesn't contain triangles and quadrangles then $3m \le 5n - 10$

Proof that if convex polyhedron doesn't contain triangles and quadrangles then $3m \le 5n - 10$ where $m$ is number of edges and $n$ number of vertices I don't know how to start this task but I ...
1
vote
1answer
39 views

Implementing Creative Reidemeister Type II Moves

Question. Given a Gauss Code $C$ of a knot $K \subset S^3$ with respect to a diagram $D$, how can one determine all possible Reidemeister type II moves that increase the number of crossings in $D$? ...
0
votes
0answers
25 views

Three dimensional representation of a set

A graph $G$ with vertex set $V$ has $\dim(G) \leq d$ if and only if there exists a sequence $<_{1},<_{2}, \ldots , <_{d}$ of total orders on $V$ satisfying the following conditions: the ...
1
vote
1answer
59 views

Is there a generalization for “planar graph” for any dimension?

We have the definition of planar graph, which captures the idea of all the connections "lying in a plane." Because any graph can be embedded in three-dimensional space without crossing, this ...
0
votes
1answer
9 views

Finding area of transformed plane

Let $T$ be a planar transformation from the $(u, v)-$plane to the $(x, y)-$plane that is a bijection, let $S$ be a domain in the $(u, v)-$plane, and let $R = T(S)$. If $\frac{d(x,y)}{d(u,v)} = 2$ at ...
0
votes
0answers
16 views

Common neighbours of adjacent vertices in maximal planar graphs

https://dspace.library.uu.nl/bitstream/handle/1874/842/full.pdf?sequence=1 At the bottom of page 115 of the above it states that'By planarity one can verify that every vertex v of G has at least one ...
0
votes
0answers
40 views

Graph factorisation

I have a graph having 6 vertices and its presentation is $E_{12}^4E_{13}^5E_{14}^6E_{24}^9E_{25}^2E_{35}^9E_{36}L_5^4L_6^{14}$. This means that there are $4$ edges connecting the vertices $1$ and $2$, ...
0
votes
0answers
28 views

combinatorics of connected components of a bicolored polyhedron skeleton

Consider the skeleton of a 3-dimensional convex polyhedron with all vertices being either red or black. We have n red and m black vertices. n < m. Take the largest sub-graph that consists of black ...
2
votes
0answers
35 views

Real world application of finding all simple paths on a graph

I am currently designing a general purpose graph database. Recently I have started to consider supporting the "find all simple paths between two nodes" operation on the graph. However while there are ...
5
votes
1answer
110 views

Correct non-inductive proof of Euler's Formula $|V|+|F|-|E|=2$?

Theorem: The number of vertices $|V|$, edges $|E|$, and faces $|F|$ in an arbitrary connected planar graph are related by the formula $$|V|+|F|-|E|=2$$ Proof Attempt: (For acyclic planar graphs) Let ...
4
votes
1answer
301 views

How to determinate the the number of crossing points?

This question is an extension of the question: how-to-determine-the-convergence-the-start-and-the-finish-points. One can apply the next algoritm and obtaine the ...
1
vote
0answers
23 views

Merge two road maps using graph theory

There are two road maps represented as a set of vertices and edges. Maps cover different areas so I want to merge two maps. An example of two maps (red and blue). The segment between two stars ...
1
vote
1answer
88 views

Find a formula, in terms of n and k , for the number of leaves of G.

Let G be a tree having n n vertices. Suppose that every vertex in G which is not a leaf has degree k, where k > 1 . Find a formula, in terms of n and k , for the number of leaves of G. I started ...
0
votes
1answer
17 views

Prove that a series-parallel hamiltonian graph is outerplanar.

A graph is series-parallel (SP) iff it contains no $K_4$ minor. I know that if the graph has no $K_4$ or $K_{2,3}$ minors, it is outerplanar. So maybe there is a way to use the fact that it is ...
-1
votes
2answers
37 views

For simple planar graph

Let $G$ be a simple planar graph (without assuming "conneceted"). Then, without assuming connectedness, is it still true that $e\le3v-6$ when $v\ge3$? Certain problem states just "simple planar". ...
0
votes
0answers
23 views

Non-planar Minimum spanning tree

Is it possible there exist a non-planar MST from a set of points? consider edge distance is the Euclidean distance.
0
votes
2answers
101 views

A plane graph $G$ is $2-$face colorable if and only if $G$ is eulerian - counter example

Actually, proof is asked in here: Planar graph has an euler cycle iff its faces can be colored with 2 colors. But my question is not about proof but about why is the following graph not a counter ...
0
votes
0answers
35 views

Graph simple planar always contains cycle [formula proof] [duplicate]

Having an old book with the following exercise that buffles me (it does not contain any solution) a simple planar $G$ with n vertices and m edges.Show that if $G$ is not acyclic then $$m \leq \frac{l(...
0
votes
0answers
18 views

Is a random walk on an isoradial graph transient?

Is the random walk on an isoradial graph defined in Chelkak and Smirnov (2011) (in pages 3-4) transient? Let us define the random walk on an isoradial graph $\Gamma$ starting from $x$ by, \begin{...
0
votes
1answer
32 views

By Kuratowski's theorem this graph seems to be planar so why is it 5 colourable considering the Four Colour theorem?

o | o--o--o | o (the dashed lines represent arcs and o represents nodes) I can't see any way this graph contains a subgraph homeomorphic to K5 ...
6
votes
1answer
109 views

Proving that any planar embedding of $G$ has at least $4$ triangular faces

Let $G=(V,E)$ be a connected simple planar graph whose edges can be colored red and blue so that for any vertices $u,v∈V$, there is a unique path connecting $u$ and $v$ whose edges are all red, and a ...
0
votes
1answer
125 views

How can I prove Euler's formula using mathematical induction

Using Euler's formula in graph theory where $r - e + v = 2$ I can simply do induction on the edges where the base case is a single edge and the result will be 2 vertices. A single edge also has ...
0
votes
0answers
23 views

Detect overlapping edges in a graph on a 2d plane.

What is the easiest way to detect if an edge overlaps with another edge in a constructed graph? I am trying to replicate a version of the Untangle game in Unity. Right now I am using Triangle.Net to ...
-1
votes
1answer
37 views

Dual Graph Score

Continuous graph G with the following score(degrees of it's vertices) (4, 4, 4, 4, 4, 4, 5, 5), has some planar embedding in which every face is bound by a graph cycle. Determine the number of ...
4
votes
1answer
89 views

The relationship between the Euler characteristic and the fundamental group of finite connected graphs

I have been asked to conjecture a relationship between the Euler characteristic and the fundamental group of finite connected graphs and, if possible, to prove the conjecture. We know that if the ...
2
votes
1answer
121 views

Prove that if the length of a smallest cycle in $G$ is $5$, then $m ≤ 5/3(n-2)$.

I'm working in the following graph theory excercise: Let $G$ be a connected planar graph of order $n ≥ 5$ and size $m$. Prove that if the length of a smallest cycle in $G$ is $5$, then $m ≤ 5/3(n-...
0
votes
1answer
23 views

Planar subgraph.

I have to find the greatest planar subgraph of $K_{m,n}$ where $m,n\le3$. So, I know it and i can drow the plane graph with an edge at most $6+2(m-3)$. But I can't show that the graph is the ...
0
votes
0answers
21 views

Let G be a simple planar graph on 13 vertices. Prove that at least one of G and its complement G is not planar. [duplicate]

Let G be a simple planar graph on 13 vertices. Prove that at least one of G and its complement G is not planar. Can we say that: e<=3n-6 , where n = number of vertices $n(n-1)/2$ is the total ...
1
vote
2answers
46 views

In the simple planar graph G the degree of each vertex is at least 5. Show that in this case G contains at least 12 vertices of degree 5.

In the simple planar graph G the degree of each vertex is at least 5. Show that in this case G contains at least 12 vertices of degree 5. I tried to solve it in this way: we know that for simple ...