Questions tagged [planar-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
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 ...
YoloV4's user avatar
  • 73
1 vote
1 answer
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 ...
YoloV4's user avatar
  • 73
0 votes
1 answer
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$ ...
YoloV4's user avatar
  • 73
1 vote
0 answers
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 ...
YoloV4's user avatar
  • 73
0 votes
0 answers
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 ...
Matthieu Latapy's user avatar
2 votes
2 answers
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 ...
Makogan's user avatar
  • 331
0 votes
0 answers
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 [1]: I don't understand this part: Lemma 2.11: HC-3-regular-(n-even) is NP-complete The result is obvious since ...
hhaamm's user avatar
  • 103
1 vote
2 answers
129 views

Are Control Flow Graphs(CFG) planar?

I notice there are different definitions for CFG(basic block or statement), so let's consider following definition: Given a program, each statement is a node in CFG, and $(u,v)\in E\iff \text{v is ...
LighT's user avatar
  • 103
1 vote
1 answer
58 views

Recreate a spanning tree in a grid graph given vertex descriptions

Let's assume I have graph above with spanning tree pointed out by blue edges. Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1. Vertex at position (4,2) (...
Looft's user avatar
  • 175
3 votes
0 answers
48 views

Add an edge to a planar graph and preserving the planarity

I've already posted in the Math StackExchange section, but nobody answered. I’m wondering if, given a planar graph $G$ And two vertices $v,u$, is there an efficient algorithm to know if adding the ...
L.A.'s user avatar
  • 131
1 vote
1 answer
63 views

crossings of edges of a geometric graph

I am considering geometric graphs $G=(V,E)$ where $V$ is a set of points in $\mathbb{R}^2$ and the edges are straight line segments between vertices. See the image: Now I want to calculate all pairs ...
Philip Mayer's user avatar
6 votes
2 answers
285 views

What edges are not in a Gabriel graph, yet in a Delauney graph?

It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{...
Wilhelm's user avatar
  • 123
3 votes
2 answers
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 ...
nuemlouno's user avatar
2 votes
1 answer
256 views

Minimum vertices to remove from a graph so that no path exists between two given vertices anymore

Given an undirected graph $G=\{V, E\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $...
Arkajyoti Banerjee's user avatar
3 votes
0 answers
81 views

Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
Yaroslav Bulatov's user avatar
2 votes
1 answer
120 views

Restore planar graph from vertex degrees

Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the ...
RainCatalyst's user avatar
2 votes
1 answer
81 views

Intuitive proof that all planar graphs are disk contact graphs

Planar graphs are graphs which can be drawn on the plane without edges crossing. Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. ...
J. Schmidt's user avatar
1 vote
1 answer
74 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. ...
Philip Mayer's user avatar
0 votes
2 answers
237 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 ...
Tworf's user avatar
  • 31
1 vote
1 answer
440 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, ...
Sam Winnick's user avatar
4 votes
0 answers
47 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 ...
nir shahar's user avatar
  • 11.5k
4 votes
0 answers
81 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.
oyyko's user avatar
  • 41
1 vote
1 answer
50 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 ...
Robert Rovetti's user avatar
4 votes
2 answers
1k 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 ...
Nathaniel's user avatar
  • 12.5k
4 votes
0 answers
47 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 ...
Mohbenay's user avatar
  • 319
3 votes
2 answers
503 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 <...
MrMobster's user avatar
  • 131
0 votes
0 answers
15 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 ...
void's user avatar
  • 1
0 votes
0 answers
30 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?
user3700810's user avatar
1 vote
1 answer
147 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 ...
Maitgon's user avatar
  • 23
2 votes
2 answers
1k 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 ...
Vakole's user avatar
  • 21
5 votes
1 answer
365 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 ...
Wonderful2019's user avatar
36 votes
2 answers
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 $\...
Hendrik Jan's user avatar
  • 29.8k
0 votes
0 answers
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 ...
Zach Hunter's user avatar
1 vote
1 answer
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 ...
Gary Andrews30's user avatar
3 votes
1 answer
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* ...
Thuy Guevarra's user avatar
4 votes
0 answers
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 ...
Areaperson's user avatar
3 votes
1 answer
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 ...
Venus's user avatar
  • 151
-1 votes
1 answer
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 ...
Mathieu Mari's user avatar
3 votes
1 answer
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 ...
RenX's user avatar
  • 131
2 votes
0 answers
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 ...
Mathieu Mari's user avatar
0 votes
1 answer
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 (...
Logan545's user avatar
  • 113
3 votes
0 answers
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 ...
Mathieu Mari's user avatar
3 votes
0 answers
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}$'...
michaelsnowden's user avatar
2 votes
1 answer
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 ...
michaelsnowden's user avatar
1 vote
1 answer
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 ...
ilirosmanaj's user avatar
2 votes
0 answers
159 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_{...
rohan's user avatar
  • 21
1 vote
1 answer
103 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. ...
royal with cheese's user avatar
1 vote
1 answer
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?
smapers's user avatar
  • 206
2 votes
1 answer
71 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 ...
Jack Lynch's user avatar
6 votes
1 answer
961 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 ...
Stan's user avatar
  • 63