Questions tagged [planar-graphs]
The planar-graphs tag has no usage guidance.
52
questions
0
votes
0answers
60 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$ ...
0
votes
1answer
41 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 ...
1
vote
1answer
29 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, ...
4
votes
0answers
34 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 ...
4
votes
0answers
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.
1
vote
1answer
20 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 ...
1
vote
2answers
157 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 ...
0
votes
0answers
31 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.
4
votes
0answers
42 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 ...
3
votes
2answers
117 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 <...
0
votes
0answers
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 ...
0
votes
0answers
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?
1
vote
1answer
53 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 ...
2
votes
2answers
405 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 ...
5
votes
1answer
152 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 ...
35
votes
2answers
2k views
Planar regular languages
In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
0
votes
0answers
33 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
1answer
187 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 ...
3
votes
1answer
152 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* ...
4
votes
0answers
46 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 ...
3
votes
1answer
123 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 ...
-1
votes
1answer
88 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 ...
3
votes
1answer
134 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 ...
2
votes
0answers
63 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 ...
0
votes
1answer
54 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 (...
3
votes
0answers
131 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 ...
3
votes
0answers
159 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}$'...
2
votes
1answer
254 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
1answer
151 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 ...
1
vote
0answers
144 views
Counting the number of connected components in a dynamic plane graph
I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{...
1
vote
1answer
68 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. ...
1
vote
1answer
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?
2
votes
1answer
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 ...
6
votes
1answer
716 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 ...
2
votes
0answers
292 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 ...
0
votes
0answers
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?
9
votes
1answer
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 ...
6
votes
1answer
121 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 ...
4
votes
1answer
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.
...
0
votes
0answers
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://...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
311 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 ...
2
votes
0answers
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 ...
3
votes
0answers
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 ...
2
votes
1answer
121 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 ...
3
votes
1answer
133 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$ ...
3
votes
1answer
681 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 ...
1
vote
0answers
90 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 (...
6
votes
2answers
1k 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.
...
