# Questions tagged [planar-graphs]

The tag has no usage guidance.

68 questions
Filter by
Sorted by
Tagged with
1 vote
77 views

### Number of decycling sets in a 3-regular planar graph

Defintitions: A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their ...
1 vote
65 views

### Number of maximal induced trees in a connected planar graph

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot ...
52 views

### Is the set of all duals same as the set of all planar graphs?

Let $P$ be the space of all possible planar graphs. Fact: A planar graph may have multiple duals based on its embedding. Let $D_p$ be the set of all possible duals of a planar graph $p\in P$ Let $S$ ...
1 vote
66 views

### Enumerate faces in any one embedding of a planar graph

Given: A planar undirected connected graph $G$ in which degree of every vertex is $2$ or more. Fact: A planar graph can have multiple planar embeddings. Question: Give an efficient algorithm to find ...
23 views

### Sparsest cuts of planar graphs

Several algorithms for sparsest cut (and other kinds of balanced cuts) in planar graphs have been published, like for instance: Finding minimum-quotient cuts in planar graphs, James K. Park, Cynthia ...
193 views

### Algorithm for farthest point Voronoi diagram?

I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly ...
78 views

### A 3-regular graph with an even number of vertices is planar?

I'm trying to understand Complexity of the hamiltonian cycle in regular graph problem : I don't understand this part: Lemma 2.11: HC-3-regular-(n-even) is NP-complete The result is obvious since ...
1 vote
129 views

215 views

### Maximum planar subgraph problem

Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid). Is there any library in python for finding the ...
256 views

39 views

### Practical computation time, counting spanning trees and selecting spanning trees uniformly at random

I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger ...
1 vote
192 views

### Need help to come up with definitive proofs with regard to Planar Graphs

I was working through a few problem sets and came across this question Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle ...
201 views

### How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points?

I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it. On a Euclidean plane, I have a polygon A, a set of points A* ...
58 views

### Simple proof that finding a combinatorial map of a planar graph given as an incidence matrix can be done in polynomial time?

Suppose that I have a graph $G = (V,E)$, given as an incidence matrix of edges and vertices. Suppose that $G$ is planar, that is, it can be embedded in the plane without edge crossings. I would like ...
144 views

### Why is the graph inside Graham Scan always planar

One of the ways to prove that Graham Scan constructs convex hull in linear time is using planarity of the graph obtained by running the algorithm. This graph is always planar, so according to Euler's ...
103 views

### Planar embeddings of planar graph

Let $G=(V,E)$ be a planar graph, only specified by its set of vertices and edges. Suppose $|V|=n$. According to Fary's theorem, there exists a planar embedding of $G$ with straight line segments. Then ...
216 views

### Is every planar graph a possible dual graph of a voronoi diagram?

My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar ...
83 views

### Tight condition making unit-disk-graphs planar

Here's a nice property about unit-disk-graphs : Suppose $V\subseteq\mathbb{R}^2$ is a finite set of points in the plane. Build the graph $G_V=(V,E)$ such that $(v,v')\in E$ iff $d(v,v')\le2$, where ...
60 views

### Where is the second face in a graph with 3 nodes?

I understand that to work out the number of faces of a connected planar graph, you use Euler's formula F = A - N + 2, where A is the number of arcs and N is the number of nodes. For a triangle node (...
175 views

### Is there an optimization problem on planar graphs which is APX-hard ?

I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
262 views

### Convert DAG whose transitive reduction is non-planar to a planar DAG with same transitive closure

For any non-planar DAG, we can compute the transitive reduction, and sometimes it will be planar (e.g. $K_5$). However, sometimes the transitive reduction is also non-planar. For example, $K_{3, 3}$'...
450 views

### Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?

Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar: but, by removing certain edges to ...
1 vote
217 views

### Show that graph is planar or not?

Show that the following graph is planar or not. My first assumption is that this graph is not planar, but could not find a reasonable prove (except saying that I tried drawing it in different ways in ...
159 views

1 vote
105 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?