Questions tagged [planar-graphs]

The tag has no usage guidance.

16 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
38 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 ...
4
votes
0answers
41 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
0answers
117 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
148 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}$'...
3
votes
0answers
111 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
0answers
58 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 ...
2
votes
0answers
272 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 ...
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 ...
1
vote
0answers
137 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
0answers
89 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 (...
0
votes
0answers
18 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.
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
23 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?
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 ...
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?
0
votes
0answers
46 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://...