# Questions tagged [planar-graphs]

The tag has no usage guidance.

36 questions
Filter by
Sorted by
Tagged with
0answers
32 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 ...
1answer
122 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 ...
1answer
53 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* ...
0answers
25 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 ...
1answer
65 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 ...
1answer
66 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 ...
1answer
67 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 ...
0answers
30 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 ...
1answer
43 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 (...
0answers
78 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 ...
0answers
112 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}$'...
1answer
106 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 ...
1answer
71 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 ...
0answers
114 views

1answer
420 views

### Creating a 2D map of objects given a sparse matrix of pairwise distances

I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for ...
0answers
84 views

### Is there a fast, “partial planarization” algorithm for non-planar graphs?

On "partial planarization" I understand an algorithm, which tries to reach an optimal, or nearly-optimal solution for non-planar graphs. For example, which minimizes the number of the crossing edges (...
2answers
712 views

### Algorithm to generate all planar graphs

Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc. ...
1answer
919 views

### Subgraph isomorphism in planar graphs

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-...
2answers
342 views

### Complexity of 4-coloring a map with constraints

The well-known Four color theorem states that every map which is divided into regions, can be colored using 4 colors such that no two adjacent regions have the same color. In fact, there exists a ...