22 votes
Accepted

Time complexity of counting triangles in planar graphs

The number of occurrences of any fixed subgraph H in a planar graph G can be counted in O(n) time, even if H is disconnected. This, and several related results, are described in the paper Subgraph ...
user avatar
  • 5,225
21 votes

Time complexity of counting triangles in planar graphs

Although Bart Jansen's answer solves the general case of subgraph counting, the problem of counting (or listing) all triangles in a planar graph (or more generally any graph of bounded arboricity) has ...
user avatar
15 votes
Accepted

Smallest vertex cover which is also an independent set

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the ...
user avatar
13 votes
Accepted

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

I can prove that no 4-regular graphs are 3-acyclic colorable. Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting ...
user avatar
  • 732
12 votes

Definition of Planar 3-SAT

There's a nice compilation of definitions of related NP-complete planar satisfiability problems at http://courses.csail.mit.edu/6.890/fall14/scribe/lec7.pdf One of them, planar monotone 3-sat, allows ...
user avatar
11 votes
Accepted

Does Max Planar 3-SAT admit a PTAS?

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach. This has been observed, for instance, in Theorem 17 in Pierluigi Crescenzi and LucaTrevisan: "Max NP-...
user avatar
  • 5,722
10 votes
Accepted

Is the maximum independent set in cubic planar graphs NP-complete?

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper. Bojan Mohar: "Face Covers and the Genus Problem for Apex Graphs" Journal of ...
user avatar
  • 5,722
9 votes

Partition planar graph into connected subgraphs of equal size

For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{...
user avatar
  • 1,132
9 votes
Accepted

Addding edges to spanning tree without destroying planarity

Here's an example of a graph $G$ and a tree $T$ in that graph such that you can't add very many edges from $G$ to $T$ while preserving planarity. Let $P$ be a $2n$-vertex path, and let $S$ be a set of ...
user avatar
9 votes
Accepted

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

I recommend reading Sections 7 and 14 in the excellent book by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh. In short, Gu and Tamaki give a quadratic time algorithm ...
user avatar
9 votes

Planarity of planar finite automata intersection

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, ...
user avatar
8 votes

"Snake" reconfiguration problem

Moving a snake from one position to some other is PSPACE complete. Snake is trivially in PSPACE. We give a PSPACE hardness reduction from Hearn's Nondeterministic Constraint Logic. Nondeterministic ...
user avatar
  • 562
8 votes
Accepted

NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

The following paper shows that the Hamiltonian cycle problem is NP-complete in maximal planar graphs: A. Wigderson The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs ...
user avatar
  • 5,722
7 votes

Another planar separator ref question

Here is a proof using a well-known hammer. Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges ...
user avatar
7 votes
Accepted

Efficient way to generate random planar cubic bipartite graphs

Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in: ...
user avatar
7 votes

What is simplest polynomial algorithm for PLANARITY?

I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy. First we break the graph into 3-connected components, as mentioned by Chandra ...
user avatar
  • 1,414
6 votes
Accepted

Sparser Bipartite graphs?

For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely,...
user avatar
5 votes

Graph planarity testing via adjacency matrix

Ignoring trivial responses like, recreate the graph from the matrix and apply any standard planarity algorithm, the closest I know of to a matrix-based planarity test is Whitney's planarity criterion. ...
user avatar
5 votes

Largest common subgraph of two maximal planar graphs

It's NP-complete, via a modified version of the reduction Wigderson used to prove that Hamiltonicity of maximal planar graphs is NP-complete. Careful examination of Wigderson's 1982 NP-completeness ...
user avatar
5 votes
Accepted

The existence of planar distance preserver?

Many years later, it looks like OP has finally answered his own question: Near-Optimal Distance Emulator for Planar Graphs by Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann was ...
user avatar
  • 2,313
5 votes
Accepted

Densest k subgraph problem for outerplanar graphs?

It can be solved in linear time in an even more general class of graphs: As shown in N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos Exact and approximation algorithms for densest $k$...
user avatar
5 votes
Accepted

Representations of Planar Graphs in Coq

The obvious resource for planar graphs in Coq would be the (modern port of) the four color theorem in Coq/SSReflect, by Georges Gonthier (and others) which obviously does need to define planar graphs. ...
user avatar
  • 13.2k
5 votes
Accepted

NP-hardness of a planar SAT variant

The following paper answers the question in the affirmative – the variant remains NP-hard using a reduction from Monotone Planar 3-SAT: http://epubs.siam.org/doi/abs/10.1137/1.9781611976465.105 (arXiv:...
user avatar
  • 141
5 votes
Accepted

Are there non trivial 2-basis of a 2-connected planar graph?

The cycles of a 2-basis (and the one leftover cycle formed from the symmetric difference of all these cycles) necessarily form the faces of a planar embedding of the graph. First, all edges of the ...
user avatar
4 votes
Accepted

Finding outer face in plane graph (embedded planar graph)

First, suppose that your arcs are embedded to the plane as straight lines. Then, the following three step algorithm works. First, compute the leftmost vertex (as David Eppstein suggested). This ...
user avatar
4 votes
Accepted

Partition planar graph into connected subgraphs of equal size

Compute a constant degree spanning tree $T$ of your graph, root it, and now greedily find subtrees of roughly size $r$, extract them, and repeat. Naturally, if there is no constant degree spanning ...
user avatar
4 votes
Accepted

Making planar graph biconnected

One way to augmenting an embedded planar graph (i.e. a plane graph) to become biconnected, while preserving the embedding, is for each articulation vertex v: for each two edges vu and vw that are ...
user avatar
4 votes

Representations of Planar Graphs in Coq

I just wanted to make some additional comments not already covered by Cody's nice answer, and also address question (2). First, Gonthier goes into detail about the representation of planar maps used ...
user avatar
4 votes

Producing colouring of maximal planar graphs G from colouring of dual of G

The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy ...
user avatar
3 votes
Accepted

How hard is it to determine the chromatic number of a unit distance graph?

Okay, this seems easy. Below I sketch why it is NP-hard to decide if a unit distance graph has a $3$-coloring. They key observation is that in a $3$-coloring any two vertices $u$ and $v$ at distance $\...
user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible