The planar-graphs tag has no wiki summary.
7
votes
4answers
230 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
108 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
129 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
241 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
422 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
146 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
149 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
150 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
309 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
211 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
106 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
182 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
407 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
75 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
125 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 ...
