The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [planar-graphs]

The tag has no usage guidance.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
26 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 ...
85 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 ...
124 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}$'...
104 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 ...
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 ...
186 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 ...
64 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 ...
126 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 ...