Questions tagged [planar-graphs]

The tag has no usage guidance.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
36 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 ...
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.
46 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 ...
49 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 ...
56 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 ...
136 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 ...
178 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}$'...
116 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 ...
70 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 ...
68 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 ...
307 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 ...
70 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 ...
29 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 ...
27 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 ...