# Tag Info

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 ...
• 5,225

### 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 ...
• 50.3k
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 ...
• 26.4k
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 ...
• 732

### 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 ...
• 50.3k
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-...
• 5,722
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 ...
• 5,722