# Tag Info

21

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.

20

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), ...

18

Being 4-colorable? Certainly MSO, and trivial on planar graphs. It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.

16

This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along ...

16

This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See http://arxiv.org/abs/1203.5944

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 = ... 14 Using nested dissections you can even solve a linear system (based on a planar graph) in$O(\sqrt{n^\omega})$. This was for example noted in a paper I have with Günter Rote and Ares Ribó and in this paper by Alon and Yuster. The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in$O(\sqrt{n^...

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

Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a ...

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

10

This question is incomplete without specifying what information about the graph as it changes you want your dynamic graph data structure to output or support queries for. But the following paper is likely relevant, even though it is described in a more general setting of combinatorial embeddings in arbitrary genus rather than just planar. It definitely ...

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

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

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

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

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 ...

8

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 ...

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

Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form. $$L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$ Now, you could use experiments on smaller-size problems to ...

6

To prove that every tree with two or more internal nodes gives you a 3-colorable graph, use induction on the number of nodes of the tree. If you orient the tree from an arbitrarily chosen root node, there always exists an internal node $v$ whose children are all leaves. Now split into cases: If $v$ has one child, then the graph can be reduced down to ...

6

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 ...

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 ...

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