Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

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

1
vote
1answer
24 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
25 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
73 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
55 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
19 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
145 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
84 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
38 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
24 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
56 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
15 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
33 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
99 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
295 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
19 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
76 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
36 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
20 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
85 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
17 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
31 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
100 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
103 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
16 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 ...
3
votes
1answer
79 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
116 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
1answer
35 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 ...
2
votes
1answer
50 views

A convex polyhedron has 20 vertices and 12 faces. Each face of the polyhedron is bounded by the same number of edges. What is this common number?

A convex polyhedron has 20 vertices and 12 faces. Each face of the polyhedron is bounded by the same number of edges. What is this common number? If I am not mistaken , "this common number" is the ...
2
votes
1answer
29 views

Is there a simple connected plane graph which has half as many vertices as regions? [closed]

Is there a simple connected plane graph which has half as many vertices as regions? How to solve this question? Thanks in advance!
1
vote
1answer
45 views

Prove $C_n^2$ is planar

Given a graph $G$, $G^2$ is defined as the graph with the same vertex set and $E(G^2) =E(G) \cup {xy: \exists z s.t. xy,zy \in E(G)}$ or simply we add edges between vertices of distance 2. I need to ...
0
votes
0answers
49 views

To express distance matrix of a graph in terms of known matrices.

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. Let $A$ denote the adjacency matrix of $G$ and $D$ denotes the distance matrix of $G$. If the graph $G$ has the diameter at most $2$ ...
3
votes
1answer
55 views

Constructing a graph with radius two.

From cycles $C_n$, $n\geq6$, I was trying to form a new graph by adding a single vertex to $C_n$ so that the added vertex has eccentricity two and rest have three. I tried for $C_6$ and $C_7$ as given....
1
vote
1answer
54 views

Connected planar graph with $n \geq 4$ vertices and $m$ edges, all edges in a cycle and no 2 3-cycles share an edge: show $m \leq \frac{12}{5}(n-2)$

This was a question I came across whilst revising for a graph theory exam. I cannot see a way to begin tackling this problem. Thus far I have tried to go along the lines of the proof for the general ...
1
vote
1answer
72 views

Generating the $n^{th}$ full binary tree over $N$ labeled leaves

I am looking for an algorithm to incrementally generate distinct full binary trees over $N$ unique leaves. That is, I want an algorithm that can generate the $n^{th}$ distinct tree without generating ...
0
votes
1answer
19 views

let H be minor of a graph G. Is it always true that embedding surface of H is less than embedding surface of G

let $H$ be minor of a graph $G$. Is it always true that (genus of embedding surface of $H$) is $\leq$ (genus of embedding surface of $G$).
7
votes
1answer
91 views

A new graph invariant? The maximum number of non-equivalent colorings with $n$ colors.

Consider (proper) coloring of a finite graph $G$ with exactly $n$ colors and the following coloring transformation: choose an edge of the graph with the end nodes of colors $a$ and $b$ and swap the ...
1
vote
1answer
31 views

Algorithm for generating a graph based on a planar graph?

I have a planar embedding of a graph, $G(V,E)$. The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each ...
5
votes
1answer
103 views

Finding $K_{3,3}$-subdivision when adding edge to maximal planar graph.

I'm working on the following problem. Show that adding a new edge to a maximal planar graph of order at least 6 always produces subdivisions of both $K_5$ of $K_{3,3}$. I had no trouble getting ...