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 ...
Ryan Williams's 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 ...
isaacg's user avatar
  • 806
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-...
Gamow's user avatar
  • 5,772
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 ...
Gamow's user avatar
  • 5,772
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 ...
Alex Golovnev's 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, ...
Hermann Gruber's user avatar
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 ...
Gamow's user avatar
  • 5,772
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: ...
Noam Zeilberger's user avatar
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 ...
Chandra Chekuri's 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 ...
GMB's user avatar
  • 2,403
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:...
squire's user avatar
  • 141
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. ...
cody's user avatar
  • 13.9k
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$...
Christian Komusiewicz's 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. ...
David Eppstein's user avatar
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 ...
David Eppstein's 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 ...
David Eppstein's 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 ...
David Eppstein's 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 ...
Noam Zeilberger's user avatar
3 votes
Accepted

Reachability Query for Tree

Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the ...
smapers's user avatar
  • 849
3 votes
Accepted

the shorstest cycle containing two given points

The problem of finding the shortest simple cycle through two vertices in a weighted undirected graph can be solved in the same time as Dijkstra's algorithm for a single shortest path, by applying ...
David Eppstein's user avatar
3 votes
Accepted

Reduction graph to planar bounded treewidth and bounded diameter graph

The diameter of $G'$ will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge $O(n)$ times, so the diameter can blow up by a factor of $O(n)$.
Laakeri's user avatar
  • 1,766
3 votes
Accepted

Is balanced Hamiltonian cycle NP complete on maximal plane graphs?

Yes, it is still $NP$ complete. This is because of: Claim: All Hamiltonian cycles on maximal planar graphs are balanced. Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/...
Elle Najt's user avatar
  • 1,439
3 votes

Finding outer face in plane graph (embedded planar graph)

It appears to me that the best way to determine the unbounded face is to compute the signed area of each face. All faces have one sign, and the unbounded face has the opposite sign. You can use the ...
Para Parasolian's 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 $\...
domotorp's user avatar
  • 14.1k
3 votes

Efficient way to generate random planar cubic bipartite graphs

In case anyone else is looking for a practical answer: the program plantri by Brinkmann and McKay can generate small (up to 64 vertices as-is, up to 255 with some hacking) planar bipartite cubic ...
delete000's user avatar
  • 818
3 votes
Accepted

Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$ Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$ To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$...
yangpliu's user avatar
  • 169
3 votes
Accepted

3-colourability of Eulerian maximal planar graph

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of ...
David Eppstein's user avatar
3 votes
Accepted

Is a grid graph a vertex-minor of a complete graph?

Vertex-minors of complete graphs are either complete graphs, star graphs, or edgeless graphs, so this does not hold for $k \ge 2$. Proof that vertex-minors of complete graphs are complete, star, or ...
Laakeri's user avatar
  • 1,766
3 votes
Accepted

Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time

I don't know whether this has been explicitly stated anywhere, but it follows from known results. Every planar graph is a minor of a $O(n)\times O(n)$ grid and such an embedding can be found in linear ...
user67422's user avatar
  • 144
2 votes

Weighted Min-Cut in bounded-genus graphs

For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying ...
Arnaud's user avatar
  • 834

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