Skip to main content

Questions tagged [planar-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
47 votes
0 answers
1k 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 ...
Michael Lampis's user avatar
32 votes
4 answers
2k views

What is simplest polynomial algorithm for PLANARITY?

There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm ...
domotorp's user avatar
  • 14k
23 votes
1 answer
2k 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, ...
Bill GASARCH's user avatar
22 votes
1 answer
472 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? ...
Jeffε's user avatar
  • 23.2k
18 votes
2 answers
2k views

Time complexity of counting triangles in planar graphs

Counting triangles in general graphs can be done trivially in $O(n^3)$ time and I think that doing much faster is hard (references welcome). What about planar graphs? The following straightforward ...
SamiD's user avatar
  • 2,319
18 votes
0 answers
548 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 ...
Aaron Schild's user avatar
17 votes
4 answers
621 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 ...
Shiva Kintali's user avatar
17 votes
0 answers
431 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 which ...
Bart Jansen's user avatar
  • 5,275
15 votes
2 answers
570 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 u, v ...
Hsien-Chih Chang 張顯之's user avatar
15 votes
1 answer
516 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 ...
Shiva Kintali's user avatar
14 votes
6 answers
564 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 ...
Sariel Har-Peled's user avatar
14 votes
4 answers
1k views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

A planar graph is a graph which can be embedded in the plane, without having crossing edges. Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k. ...
R B's user avatar
  • 9,458
14 votes
1 answer
2k 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 ...
user197284's user avatar
13 votes
1 answer
420 views

Planarity of planar finite automata intersection

It was shown that any regular language can be specified by planar $\varepsilon$-free nondeterministic finite automaton (Bezáková, Ivona, and Martin Pál. "Planar finite automata."). Is it ...
gsv's user avatar
  • 421
13 votes
1 answer
578 views

"Snake" reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
Marzio De Biasi's user avatar
13 votes
1 answer
854 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 ...
Vinayak Pathak's user avatar
12 votes
0 answers
365 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 ...
Thang Dinh's user avatar
11 votes
1 answer
437 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 ...
Shiva Kintali's user avatar
11 votes
2 answers
3k 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 $...
user771871's user avatar
11 votes
0 answers
131 views

s-t connectivity on infinite planar graphs with finite description

I would like to know if the following problem is known and has been studied: Consider an infinite directed graph that can be built on the infinite lattice "tiling" a finite set of subgraphs, ...
Marzio De Biasi's user avatar
11 votes
0 answers
306 views

A bijection between ordered lambda terms and rooted planar maps?

Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{...
Noam Zeilberger's user avatar
10 votes
1 answer
300 views

Is there a planar 4-regular graph that is 3-acyclic colourable?

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours). Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
Cyriac Antony's user avatar
10 votes
1 answer
1k views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
user24175's user avatar
  • 375
10 votes
1 answer
875 views

3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
Zach Hunter's user avatar
10 votes
1 answer
263 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 ...
Yixin Cao's user avatar
  • 2,559
9 votes
2 answers
314 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 ...
arnab's user avatar
  • 7,010
9 votes
4 answers
2k views

Partitioning graphs while minimizing inter-partition edges

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
zaloo's user avatar
  • 393
9 votes
1 answer
920 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 ...
eold's user avatar
  • 233
9 votes
2 answers
557 views

NP-hardness of a planar SAT variant

Background: An instance of 3-SAT is called monotone if each clause consists only of positive literals or only of negative literals. Given an instance $\phi$ of 3-SAT, we consider the bipartite graph $...
squire's user avatar
  • 141
9 votes
1 answer
2k 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 ...
Javad's user avatar
  • 251
8 votes
1 answer
318 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 ...
user197284's user avatar
8 votes
1 answer
157 views

Another planar separator ref question

Do any of you know a reference for the following (surprisingly tedious to prove) result? Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \...
Sariel Har-Peled's user avatar
8 votes
1 answer
973 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of vertices ...
Austin Buchanan's user avatar
8 votes
0 answers
172 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

Given a planar graph $G=(V,E)$, there exists a quadratic algorithms for 4-coloring $G$ (and $G$ is surely 4-colorable). Assume you are given a set of $k$ constraints of the form "$v_i \text{ is ...
R B's user avatar
  • 9,458
8 votes
0 answers
172 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 ...
Florent Foucaud's user avatar
7 votes
2 answers
2k views

Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for 4-...
ivmihajlin's user avatar
7 votes
1 answer
363 views

Does Max Planar 3-SAT admit a PTAS?

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each ...
Mathieu Mari's user avatar
7 votes
4 answers
772 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 wasn'...
user15735's user avatar
7 votes
1 answer
389 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$, ...
beauby's user avatar
  • 221
7 votes
0 answers
181 views

Algebraic methods for testing planarity

Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
Will's user avatar
  • 215
7 votes
0 answers
317 views

reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected ...
Noam Zeilberger's user avatar
7 votes
0 answers
240 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 easy ...
Yixin Cao's user avatar
  • 2,559
7 votes
0 answers
395 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 ...
Aaron Sterling's user avatar
6 votes
1 answer
2k 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 ...
Veehmot's user avatar
  • 163
6 votes
1 answer
364 views

Complexity of optimal elimination for a planar tensor network

Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question Suppose we need to sum out variables in a tensor network (a factor graph where each ...
Yaroslav Bulatov's user avatar
6 votes
0 answers
120 views

Enumerating homologies of disjoint paths

I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths. I did not understand how do they re-route the paths through a spanning tree and ...
kishlaya's user avatar
  • 191
6 votes
0 answers
85 views

Fáry-Like Theorems for nonplanar graphs

Let $cr(G)$ be the crossing number of a graph $G$, i.e. the minimum possible number of edge crossings over all valid drawings of $G$ in the plane. In general the edges of $G$ may be represented as ...
GMB's user avatar
  • 2,403
6 votes
0 answers
93 views

How much is known about coloring of planar graphs with degree bounds?

Are there any references that address the following (open?) questions: 1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time? 2) What is the largest ...
Tommy R. Jensen's user avatar
5 votes
2 answers
552 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 ...
Graviton's user avatar
  • 409
5 votes
2 answers
323 views

Efficient way to generate random planar cubic bipartite graphs

3-regular bipartite planar graphs appear in a variety of NP- / #P-complete problems. Suppose one wants to test the complexity of these problems via numerical experiments. Is there an efficient way to ...
delete000's user avatar
  • 828