# Questions tagged [planar-graphs]

The tag has no usage guidance.

53 questions
Filter by
Sorted by
Tagged with
42 views

### Similarity measures for (geometric) triangulations

In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $S$. I would like to cluster similar triangulations. ...
61 views

### Feedback Vertex Set restricted to planar graphs

In Feedback Vertex Set, we are given an undirected graph $G$ and $k \in \mathbb{N}$, and the objective is to decide whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that $G-S$ ...
48 views

### How to Draw the planar embedding of a graph?

I am very interested to know how to draw the planar embedding of a graph. For this graph: I cannot find the planar embedding because it is a Peterson graph, which is not planar; but for the following ...
36 views

### What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?

How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$? In the post linked above, the user "plop" gives a great response where they claim, in particular, ...
35 views

### Planarity testing given an embedding

I am given a connected graph $G$ with some embedding. I want to find a non-deterministic algorithm running in $O(n)$ time to decide whether $G$ with that embedding is a plane graph (i.e, can be drawn ...
80 views

### If a graph has $15$ vertices, one with degree $8$, $6$ with degree $6$, $8$ with degree $4$, is it a planar graph?

The question is as above. I want to prove that there exists a $K_5$ as a subgraph, so this graph is not a planar graph. But I failed. If you can help me, I will be very appreciative.
23 views

### Are there any established methods for generating random graphs/networks that are both planar and meshlike?

There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am ...
189 views

### How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the ...
34 views

### Boruvka in planar graphs

On wikipedia it says that boruvka can be implemented in linear time for planar graphs, but I don't know how to prove that.
43 views

### Decomposing planar Hamiltonian graphs

I have the following the statement and I have to prove whether it is true or not. Given a planar and Hamiltonian graph $\mathbb{G} = (V, E)$, show that we can partition $E = E_1 \cup E_2 = E$ so that ...
138 views

### Finding closest edge to a point in a planar graph

I have a point location problem (in a planar graph) with a twist: rather then finding which region the point is located in, I would like to find the closest segment (edge) to a point, ideally with a <...
12 views

### How to remove filaments from a planar graph?

I have a planar graph and I'm trying to implement this algorithm (https://geometrictools.com/Documentation/MinimalCycleBasis.pdf Chapter 4, page 3). For the filament F0(V4, V3, V2), that has one ...
24 views

### planar 1-in-3 sat described as a planar graph for independent set

Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?
59 views

### Max independent set in planar graphs PTAS proof

I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone ...
507 views

### Clique-problem for planar graph

I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion This follows already from Kuratowski's theorem: a clique is at ...
173 views

### Near Triangulation Planar Graph

This is the problem I am dealing with: Given a set P of n points in general position, let a graph G be defined as follows: The vertex set is P. Two vertices, a and b, are joined by an edge provided ...
2k views

71 views

### Infinite sequence of graphs

http://jgaa.info/accepted/2011/HasheminezhadMcKayReeves2011.15.3.pdf Hello I stumbled upon this paper. On page $4/20$ the figure shows an infinite sequence of $5-$regular, connected planar graphs. ...
97 views

### Planar graphs of bounded degree: mixing time = cover time?

For many planar graphs of bounded degree (binary tree, lattice, cycle) the (1/4)-mixing time and the cover time are equal, up to log-factors. Is this always the case?
53 views

### Planar Embedding with Some Nodes Constrained

I've read about basic planar-graph embedding and about embedding a planar graph onto a set of fixed points, but I was wondering how one might constrain the locations of some nodes—perhaps to a set of ...
733 views

### Why graph planarity is important

What is the reason to study planar graphs and algorithms on such graphs (as well as algorithms allowing to check a graph's planarity)? Where in industry this knowlege is needed? I know that planarity ...
293 views

### FPT: Dominating Set on Planar Graphs (average degree is known)

I'm given an instance of a planar graph and should construct a FPT algorithm for dominating set. The task looks like this: Dominating Set on Planar Graphs Instance: A planar graph G and an integer ...
25 views

### Planar cover of a rigid and non-planar graph

Let $G$ be a graph which is rigid and non-planar (e.g. $K_{3,3}$). Is it possible that $G$ has a planar cover? Are there any studies on this topic?
2k views

### Treewidth of k x k square grid graphs

According to some slides I found on google, the treewidth of any $k \times k$ square grid graph $G$ is $tw(G) = k$. I just started researching about treewidth and tree decomposition, and for the most ...
127 views

### Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes

I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph ...
1k views

### Converting a non-planar graph to planar

Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness. ...
50 views

### Complete set of basic circuits for McLane's Theorem

I was assigned a project in which i had to implement some algorithms concerning graphs. The last one is the one described in the title. I have to make an algorithm that uses McLane's theorem (https://...
24 views

### Maximum Weight Planarization of Size $n$ [duplicate]

Problem: Maximum Weight Planarization Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges. Find the subgraph with $n$ nodes (but possibly removing edges to ...
227 views

### Finding one face in planar graph

Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle. How do we find ...
313 views

### A criterion for the planar graph to have unique dual

I get stuck with the following two criteria both about the uniqueness of plane embeddings of a given planar graph. The first one says that a planar graph admits unique plane embedding iff it is a ...
65 views

### Closed walk in planar graphs that contains $k$ faces

Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$. Output: A shortest closed walk (one among possibly many, if exists) in $G$ using $e$ and $f$ which ...
114 views

### Planar TSP: no node insertion?

Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the ...
124 views

### Upper bound on the number of triangles in a planar graph

For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller ...
134 views

### Partitioning planar graphs without minimizing edge cuts

I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions: Creates balanced (within some margin) $k$ partitions of $V$ ...