The planar-graphs tag has no wiki summary.
10
votes
0answers
222 views
Complexity of the densest k-subgraph problem on planar graphs
In the densest k-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
6
votes
4answers
303 views
3-coloring of specific planar graphs
Consider any tree $T$ with $n>2$ vertices and $k$ leaves. Let's denote $G(T)$ a graph constructed from $T$ by connecting its leaves into $k$-cycle in such way that $G(T)$ is planar.
In case I ...
2
votes
1answer
118 views
Dynamic all-pairs shortest paths - O(1) query
I'm trying to come up with an algorithm to solve all-pairs shortest paths (APSP) problem in dynamic directed planar graph with nonnegative real weights. Additionally:
My primary focus is to achieve ...
7
votes
1answer
136 views
Fitting minimum number of rectangles of width/height 1 into a 2D grid
Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied
and you need to put the minimum number of non-overlapping rectangles of any size w x h where ...
21
votes
1answer
246 views
Exact planar electrical flow
Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor. How quickly can we compute the exact effective resistance between two vertices in G? ...
27
votes
0answers
432 views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
11
votes
1answer
149 views
An improper planar coloring with monochromatic component size $\leq 2$
Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the ...
6
votes
1answer
153 views
Understanding bounded-diameter decomposition of graphs for PTAS
While trying to understand Baker's approach (also explained in this article by Eppstein) to designing PTAS's for planar graphs, I came across a difficulty.
The idea is, given an integer $k$, ...
7
votes
1answer
157 views
Fast deletion / contraction in combinatorial embedding
I wonder if there is a sublinear algorithm to make deletion or contraction of an edge in a combinatorial embedding of, lets say, planar graph?
Since in combinatorial embedding we have to maintain ...
9
votes
1answer
319 views
What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?
$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that ...
10
votes
1answer
215 views
MSO properties, planar graphs and minor-free graphs
Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known ...
1
vote
2answers
107 views
Maximum Crossing number of topological graph
The crossing number of a graph $G$ is defined as the least number of crossings introduced when $G$ is drawn as a topological graph in the plane.
Is there anything known about the maximum number of ...
10
votes
1answer
192 views
Combinatorial embedding of a graph
Here : http://www.planarity.org/Klein_elementary_graph_theory.pdf (in chapter embeddings) is given definition of combinatorial embedding of a planar graph. (with definition of faces and so on) Though ...
16
votes
3answers
409 views
Hard Problems for higher genus graphs
Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :
Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs ...
7
votes
0answers
76 views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it seems that ...
3
votes
2answers
129 views
Algorithms for creating a directed network with a given 3-node motifs distribution
I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in ...
4
votes
0answers
125 views
Can we achieve a better kernel for the Vertex Cover problem on planar graphs?
We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC.
My question is, can we do better for planar graphs? It is ...
13
votes
1answer
341 views
Decomposing graphs of genus one
Planar graphs are $K_{3,3}$-free. Such graphs can be decomposed into tri-connected components, which are known to be either planar or $K_5$ components.
Is there such a "nice" decomposition of ...
4
votes
1answer
260 views
On planarity in two related graphs
Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.
My simple question is: Is there a ...
20
votes
1answer
1k views
I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)
It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.
Is there a nice gadget that will, ...
12
votes
0answers
215 views
Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?
I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals ...
10
votes
1answer
429 views
Covering a simple polygon with circles
Suppose I have a simple polygon $S$ and an integer $k$. What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$? How about if ...
0
votes
0answers
130 views
How to detect dead ends on a board / in a graph?
Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of ...
5
votes
1answer
496 views
Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed
Update:
This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution.
http://www.youtube.com/watch?v=VbSwwos4R2E
I want to ...
9
votes
0answers
207 views
Directed Sparsest Cut on Planar Graphs?
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
10
votes
0answers
291 views
Largest common subgraph of two maximal planar graphs
Consider the following problem -
Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and ...
14
votes
6answers
456 views
Planar graph via the intersection of fat thingies?
There is a beautiful theorem of Koebe (see here) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be ...
8
votes
1answer
266 views
The existence of planar distance preserver?
Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals. A distance preserver of (G,T) is a graph H satisfying the property
$$d_H(u,v) = d_G(u,v)$$
for all nodes ...
5
votes
2answers
260 views
Graph planar drawing, with each edge's length is known
Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not.
Further assume that this is a graph that can be embedded ...
8
votes
2answers
258 views
Drawing graphs of bounded crossing number
Fáry's theorem says that a simple planar graph can be drawn without crossings so that each edge is a straight line segment.
My question is whether there is an analogous theorem for graphs of bounded ...
6
votes
0answers
218 views
Embedded dynamic programming (and planar subgraph isomorphism)
In Planar Subgraph Isomorphism Revisited, Frederic Dorn obtains an improved algorithm for Planar Subgraph Isomorphism, by using a technique he calls Embedded Dynamic Programming. This technique ...
2
votes
1answer
427 views
Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs
Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs.
Has a similar ...
