Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

20

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.

19

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

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

No. At least, no "nice" gadget for one crossover. Let $(a, b)$ and $(x,y)$ be a cross we want to replace. There are many cases for our graph, $G$, but we have to satisfy at least the following four. Case 1: there is at least one hamiltonian cycle, but none use either of the edges. Case 2: there is at least one cycle, and all cycles use exactly one of ...

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

Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO. One can get 1+eps approximation algorithm using sliding grids. It is natural to assume the problem is NP-Hard because of the work by Feder and Greene.

11

$\mathcal{G}_B$ is the bipartite double cover of $\mathcal{G}_A$. So it has twice as many vertices and edges, and if $\mathcal{G}_A$ has an embedding with $x$ even faces and $y$ odd faces then $\mathcal{G}_B$ has an embedding (possibly on a nonplanar surface) with $2x+y$ faces, formed by making two copies of each even face and replacing each odd face by its ...

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

10

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

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

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

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

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

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

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

7

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

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

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