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 ...
- 27.5k
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 to ...
- 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-...
- 5,782
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 ...
- 5,782
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 ...
- 2,247
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, ...
- 6,665
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
...
- 5,782
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:
...
- 4,561
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 ...
- 7,039
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:...
- 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.
...
- 14k
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$...
- 1,934
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 ...
- 2,461
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 ...
- 51.1k
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 ...
- 51.1k
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 ...
- 4,561
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 ...
- 51.1k
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/...
- 1,469
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 ...
- 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 ...
- 51.1k
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)$.
- 1,881
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 ...
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 $\...
- 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 ...
- 828
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.$...
- 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 ...
- 51.1k
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 ...
- 1,881
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 ...
- 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 ...
- 834
2
votes
Accepted
Finding a "lowest" path in a graph
This problem is NP-complete, by reduction from Hamiltonian cycle in a graph G=(V,E). Every edge in E receives weight 0. If a vertex is traversed, there is a gadget that allows you to use an edge of ...
- 5,782
Only top scored, non community-wiki answers of a minimum length are eligible