22

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 Isomorphism in Planar Graphs and Related Problems by David Eppstein of 1999; see Theorem 1. The paper indeed uses treewidth techniques.


21

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 been known to be linear time for much longer. See C. Papadimitriou and M. Yannakakis, The clique problem for planar graphs, Inform. Proc. Letters 13 (1981), ...


15

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 problem to 2-SAT, as follows: make a variable $x_i$ for each vertex $i$, and for each edge $(i,j)$, include clauses of length two of the form $x_i \oplus x_j = ...


13

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 either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as ...


12

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 you to split each terminal into positive and negative, with the terminals placed along a line with the positive part on one side of the line and the negative ...


11

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem. Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987. Satish ...


11

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-completeness made easy" Theoretical Computer Science 28, (1999), Pages 65-79


9

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{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed). However, the problem is polynomial for ...


9

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 $n$ points $(x_i,y_i)$ in the plane with distinct integer coordinates in the range $[1,n]$ such that the longest polygonals chains in $S$ in which all slopes ...


9

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 which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than ...


9

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 Combinatorial Theory, Series B 82, 102-117 (2001)


8

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 Constraint Logic Let a constraint graph be a directed graph with edges of weight $1$ and $2$, such that every vertex has incoming weight $\geq 2$. Given two ...


8

In a single layer of the partition, consisting of the vertices at distance $d$ to $d+k$ from the root, the vertices at distance $d+1$ through $d+k-1$ can be dominated the same way as they are in the whole graph, but you have no control of the size of the dominating sets of the vertices at distances $d$ or $d+k$, on the boundary of the layer: in the original ...


8

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.


8

Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper: http://www.cs.uiuc.edu/~jeffe/pubs/crum.html This already implies that you can encode pretty nasty ...


8

As a first remark, your focus seems to be on hypergraphs but I think that most of the literature about embedding hypergraphs prefers to work with simplicial complexes. A good reference on these questions is this paper by Matousek, Tancer and Wagner. Does Fáry's Theorem hold in higher dimension? The answer is no. There are actually 3 different notions ...


8

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 Technical Report #298, Department of EECS, Princeton University, February 1982. https://www.math.ias.edu/avi/node/820 In a maximal planar graph, every face is ...


7

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 Chekuri. Break the graph into connected components. Break each connected component into 2-connected components. This can be done in polynomial time checking for each ...


7

This paper: http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf gives an $O(n\log{n})$-time 3-colouring algorithm for triangle-free planar graphs, improving on Thomassen's $O(n^2)$-time constructive proof. I'm not exactly sure, but does this answer your question?


7

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: Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), ...


7

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 which are part of the spanning tree. I claim that the treewidth of $G$ is $O(\sqrt{t})$ which would imply the desired separator (and some more). To prove the claim ...


6

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, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are ...


6

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, whereas any equivalent planar NFA needs $\Omega(\frac{n^2}{\log\log n})$ states. The proof is indirect and goes via a lower bound on regular expression size: ...


5

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 proof of hardness for Hamiltonian cycles in maximal planar graphs (http://www.math.ias.edu/avi/node/820) shows that the instances produced by his reduction have ...


5

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. But it uses the incidence matrix, not the adjacency matrix, and is a mathematical criterion rather than a polynomial time algorithm. It states that a graph is ...


5

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$-subgraph WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125 the Densest-$k$-Subgraph problem can be solved in $O(2^{\mathrm{tw}(G)}\cdot k \cdot ...


5

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. It's not immediately obvious to me how planar graphs are characterized, though the relevant file is here and it seems to involve a combination of Euler ...


5

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: http://arxiv.org/abs/2009.12369) The paper presents a slightly more restricted variant, Monotone Planar 3-SAT with Neighboring Variable Pairs, which requires ...


5

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 graph belong to some cycle by 2-connectivity. Second, the edges appearing only once in the basis cycles must form a single cycle, else their subgraph would have ...


4

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 just posted on the arxiv. The answer to the original question is yes: it is shown that $\widetilde{O}(\min\{t^2, \sqrt{tn}\})$ edges suffice to preserve distances ...


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