A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane. In other words, there is some pictorial representation of the graph such that the edges only intersect at vertices. Consider tagging with (combinatorics) and (graph-theory).

learn more… | top users | synonyms

0
votes
0answers
9 views

Complement of a hamiltonian circuit in a 4-valent simple planar graph

Consider a 4-valent simple planar graph G. Suppose that it has no vertices which if removed would disconnect the graph. It has been proven that such a graph has a Hamiltonian circuit. It is also ...
0
votes
2answers
14 views

Each regional of a maximal planar graph is a triangle

Show that every region of a maximal planar graph is a triangle. A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph. Will this proof use the ...
2
votes
1answer
35 views

finding edges of a triangle graph from degrees of points

my theory: Given a list of points on a 2 dimensional plane, and the degree of each point, there should correspond only one way to arrange the edges between points so that the final graph is a mesh of ...
1
vote
0answers
20 views

Abstract dual of a graph and $K_{3,3}$

Let $G$ be a graph. The abstract dual of $G$ can be defined as a graph $G^*$ whose edges are in one to one correspondence with $G$ and whose spanning trees are obtained by taking the complements of ...
1
vote
0answers
17 views

Automorphism group of planar graphs

I am going through Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. It has shown that the automorphism group of a planar graph $G$ is as follows. $$ \text{Aut} ...
0
votes
0answers
25 views

Kuratowski's theorem proof: Flappable bridges

I have a doubt concerning the proof of Kuratowski's theorem. The proof I am reading from is from Combinatorial Problems and Exercises by Lovasz. (Pg 299-301). We are given a graph $G$ which is a ...
1
vote
1answer
30 views

$G$ a maximal simple planar graph with $n$ vertices, $m$ edges and $ki$ vertices of degree $i$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$.

$G$ is maximal simple planar graph with $n$ vertices and $m$ edges. There are $ki$ vertices of degree $i$, for $i = 1, \dots, n-1$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$. I got the following ...
3
votes
0answers
36 views

Automatic solver of four-color theorem?

Does anyone know of an app/online tool to automatically colour any map or image using the 4-colour theorem? (Taking a Black and white image as input).
1
vote
1answer
27 views

How to find a planar graph if I know that it has 7 faces with certain sizes?

I can't figure out how to find a graphs with this properties: I have to find 2 non-isomorphic plane graphs which (each of them) have 7 faces, two of which are of size 3 and the rest of size 4. This ...
1
vote
1answer
28 views

Maximum number of edges of a planar graph without cycles of length 3 and 4

I'm trying to calculate the maximum number of edges in a planar graph without cycles of length $3$ and $4$ (thus, $C_3$ and $C_4$). I've assumed that the condition is that the length of each face has ...
1
vote
1answer
85 views

Highest possible number of edges in a planar graph, which does not contain C3 or C4

Determine the highest possible number of edges in a planar graph, which does not contain C3 or C4 (C = cycle, 3,4 = length of the cycle). Details: you are given $n$ vertices and they are asking you ...
5
votes
1answer
100 views

A doubt in the proof of Kuratowski theorem

In trying to understand the proof of Kuratowski's theorem (namely, a graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$) from this book (Page 299) I am first trying to ...
0
votes
0answers
24 views

Result of LexBFS on an outer-planar graph

Suppose we have an outer-planar graph $G$. Is the following expression true? If yes, please prove it. If no, please give a counterexample. After running LexBFS on $G$, we will have a vertex order ...
3
votes
2answers
50 views

Guaranteeing a path is on the outer face of a planar graph

Let $G$ be a planar graph containing a path $P$. Is it always possible to draw $G$ in the plane so that the path is on the outer face? If the path consists of a single edge then one can use ...
0
votes
0answers
15 views

Prove that if $G$ is planar graph with $\delta(G) \geq 3$ and less than $12$ faces, then its girth is less than $4$

I'm not really sure how could I use the fact that $\phi(G)$ < 12. Since $\delta(G) \geq 3$ I have: $2e(G^*)= 2e(G) \geq 3|G|$ where $G^*$ is dual graph, so: $\sum_{f \in F(G)} deg(f) \geq ...
0
votes
0answers
29 views

What is the definition of Planar $3$-Sat problem?

I have some steps in my lecture-notes to make an instance of Planar $3$-Sat problem from an instance of $3$-Sat problem. The steps are as follows: Create one vertex for every literal $x_i$ Create ...
3
votes
0answers
34 views

maximum edges in a planar graph without 3 and 4 cycles

What is the largest possible number of edges in a plane graph without 3-cycles and 4-cycles? I've been unsuccessfully trying to solve this problem from my book. I know that every plane graph without ...
2
votes
1answer
22 views

Graphs embeddable into tree like simplicial 2-complexes

A tree gives rise to a simplicial 1-complex. A tree like simplicial 2-complex would be simplicial 2-complex without any closed 2-subcomplexes (the analog of a cycle in graphs) and such that the ...
0
votes
1answer
28 views

Question about circuits in a planar graph (length)

I need to show that a circuit in a planar graph that encloses two regions, and each region has an even number edges, has an even length. Could someone point me in the right direction as to how to ...
3
votes
1answer
37 views

Every bridgless planar 3-regular graph is 3-edge colorable

How to prove an implication Every bridgless planar 3-regular graph G is 3-edge colorable. I know: From Vizing Theorem, that I can color G with 3 or 4 colors. I have a hint to use that we have ...
0
votes
1answer
62 views

Prove that each closed cycle in $G$ has a minimum length of $5$.

Given the following graph $G$: How can I prove that each cycle in $G$ has a minimum length of $5$?
2
votes
1answer
41 views

Regular graphs and planarity

Being new to the real of Graph theory, I came across this problem where it was asked to find the number of regions in the planar depiction of G, where G=(V,E), loop-free, connected 4-regular planar ...
0
votes
1answer
12 views

Formula to find an angle of point on a coordinate plane

Given a plane and an arbitrary (x,y) point, is there a succinct formula to find the angle of that point against the positive y-axis? For example, pictured below the green point is 0 degrees, blue 45 ...
1
vote
0answers
22 views

outerplanarity of grid graph

I was asked to compute the outerplanarity of (n x m)-grid graph where a given hint was "a grid doesn't need to be drawn as a grid. There are also other ways to draw it!". So, I tried to redraw a 4x5 ...
0
votes
0answers
19 views

Redrawing a planar graph with straight edges

Recently in my undergraduate graph theory course we started learning about planar graphs. Now, the concept is very easy to me - However, in the homework, we are asked to redraw a certain graph as ...
2
votes
1answer
70 views

Total number of edges in a triangle mesh with $n$ vertices

Given a 2D triangle mesh with $n$ vertices, I was wondering if there is an expression that would allow to compute the total number of edges present in the mesh. For example, this mesh has 6 vertex ...
5
votes
1answer
31 views

Fáry's theorem for infinite graphs

Fáry's theorem is a (fairly famous) statement which asserts that every finite simple planar graph can be drawn in a way such that every edge is represented by a straight line segment. Does this ...
2
votes
1answer
19 views

What would be the most efficient way to detect all closed paths in a collection of segments and connectors?

We have a data set which is comprised of Connectors and Segments. Each segment has exactly two connectors, but each connector can belong to zero or more segments (i.e. connector 'A' in the left image ...
3
votes
1answer
28 views

when do we say if two graphs are isomorphic and when do we say they are the same?

A complete graph of 4 vertices can be represented with a square and also with a triangle with a vertex in the middle. I'm confused if I should call the two graphs isomorphic or the same? Also, can ...
4
votes
1answer
50 views

Colorability of planar graphs.

I'm trying to show that every planar simple graph with no cycles of length {4,5,6,7,8,9,10,11} is 3-colourable. Here is what I've done so far. Let S be the set of all graphs for which the statement ...
0
votes
0answers
18 views

Maclane's theorem and $2$-connected graphs

Maclane's planarity criteria states that A graph $G$ is planar if and only if its cycle space has a basis such that each edge of $G$ belongs to at most two elements of it. Such a basis is called a ...
2
votes
1answer
21 views

Understanding the proof: Maclean's Planarity Criteria

Maclane's planarity criteria states that A graph $G$ is planar if and only if its cycle space has a basis such that each edge of $G$ belongs to at most two elements of it. I am reading its proof ...
0
votes
1answer
126 views

Suppose G is a connected planar simple graph with $e$ edges and $v$ vertices with no cycles of length 4 or less…

Suppose G is a connected planar simple graph with $e$ edges and $v$ vertices with no cycles of length 4 or less. Prove that (For $ v ≥ 4$): $$e ≤ {\frac{5}{3}}v - {\frac{10}{3}}$$ -I have a basic ...
1
vote
1answer
55 views

if $G$ is a connected planar graph with $|V| = v$ and $|E| =e$ and each cycle in the graph is of at least length $k$

if $G$ is a connected planar graph with $|V| = v$ and $|E| =e$ and each cycle in the graph is of at least length $k$, Prove that $e \leq { \big( \frac{k}{k-2} \big)} {(v -2)}$. I was thinking ...
1
vote
1answer
47 views

Prove that a graph is a maximal planar graph if and only if $e = 3v − 6$

Definition: A planar graph with no multi-edges $G$ is called a maximal planar graph if the graph formed by addition of any edge (not already in the $G$) is not planar or the graph is $K_3 $ or $K_4$ ...
2
votes
1answer
66 views

Show in a maximal planar graph every face is a triangle.

So I argue by contradiction as follows. Assume there exists a face in which there are more than three edges, Then the face must be a cycle, IF the face is four edges, then we can one edge and this ...
3
votes
1answer
56 views

Consequences of cycle space cut space duality

The cycle space cut space duality theorem for planar graphs states that: The cycle space of a planar graph is the cut space of its dual graph, and vice versa. I wish to know any consequences and ...
1
vote
1answer
24 views

Interesting planar graph coloring task - estimate colours for double planar graph

I got an interesting exercise on my course at University. I am wondering about an answer and I would like that some people would wonder with me. Because there may be not clear answer even. So.. as ...
2
votes
1answer
41 views

The cycle space of a planar graph is the cut space of its dual graph

I am trying to understand the following statement on wikipedia: The cycle space of a planar graph is the cut space of its dual graph, and vice versa. Suppose we have a cycle space $\mathcal ...
1
vote
1answer
13 views

Problem with planar connected graphs

For one of my homework assignments I'm being asked to list all the possible plane graphs with four vertices but surely there would be an infinite number of those? Nowhere in the question does it say ...
4
votes
1answer
85 views

Understanding the proof: A spanning tree in $G$ implies a spanning tree in dual graph

The theorem I am reading is as follows: Suppose $G$ is a connected planar graph. Let $T$ be the set of edges in $G$ which form a spanning tree and let $T^*$ be the set of all edges which are duals ...
2
votes
1answer
56 views

What mathematical principle is being used in solving planar graphs for each step you move a vertex?

Recwntly I was playing this game, which a graph is presented and the player asked to solve it by moving vertices until no intersections is possible From the related wikipedia link and the development ...
3
votes
1answer
52 views

What is a good planar graph test?

Consider adjacency matrix of $8$ vertex bipartite graph with $4$ vertices of each color: \begin{bmatrix} 0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& ...
0
votes
1answer
64 views

Are all connected graphs with Euler characteristics 2 planar?

I have read proofs and descriptions stating that a planar connected graph have the Euler characteristic 2. I'm not sure if that statement is equivalent to "a connected graph with the Euler ...
0
votes
1answer
43 views

$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ ...
0
votes
0answers
20 views

Translating position of x y onto new plane

I have two planes, both the same size, one directly in front of the other - plane A is in front and is 200 x 200, plane B is behind and is also 200 x 200. When I draw a line or rectangle or whatever ...
2
votes
1answer
201 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
3
votes
1answer
69 views

Planar graph and number of faces of certain degree

Let G be a 4 regular connected planar graph (with a planar embedding), where all faces are either degree 3 or degree 4. Then determine the number of faces of degree 3. Also, now suppose that every ...
3
votes
1answer
168 views

Prove that the graph dual to Eulerian planar graph is bipartite.

How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection
0
votes
1answer
33 views

In graph theory, what's the difference of triangles and 3-faces?

I'm pretty sure that triangles and 3-faces are not the same but I cannot find their differences according to their definitions. Could you please help me with that? Thanks