New Distributed Interactive Proofs for Planarity:
A Matter of Left and Right

In this paper, we consider distributed interactive proofs (DIPs) based on the model of [19].²²2We note that [19] uses the terms dAM and dMAM to denote the special cases of a DIP protocol with $2$ and $3$ rounds, respectively. In the DIP setting, instances are graphs $G=(V,E)$ taken from some universe $𝒰$ and the goal is to distinguish between yes-instances that come from a yes-family ${ℱ}_Y\subset 𝒰$ and no-instances that come from a no-family ${ℱ}_N=𝒰-{ℱ}_Y$.³³3One can easily adapt the setting so that instances also include some local information to the nodes (e.g., identifiers, weights, etc.). We chose to avoid this additional notation as the results of this paper apply to graphs without local node information. A DIP is an interactive protocol between a distributed verifier operating concurrently at all nodes of the graph and a centralized prover that can see the entire instance. The prover and verifier interact back and forth in rounds. Let ${ℐ}_{\mathrm{𝚟𝚛𝚏}}$ denote the rounds in which the verifier interacts with the prover and let ${ℐ}_{\mathrm{𝚙𝚛𝚟}}$ denote the rounds in which the prover interacts with the verifier.

Our protocols are public-coin which means that in each round $i\in {ℐ}_{\mathrm{𝚟𝚛𝚏}}$, the verifier at each node $v\in V$ interacts by drawing a random bitstring ${\rho }_v^i\in {\{0,1\}}^{\ast }$ and sending it to the prover (in particular, the verifier cannot hide any random bits from the prover). The prover interacts with the verifier in rounds $i\in {ℐ}_{\mathrm{𝚙𝚛𝚟}}$ by sending a message ${\mu }_v^i\in {\{0,1\}}^{\ast }$ to each node $v\in V$. Keeping up with the terminology of [20], we sometimes refer to the messages sent by the prover as labels. The interaction ends with a round in which the prover interacts with the verifier, after which the verifier at each node $v\in V$ computes a local yes/no output based on: (1) the random bitstrings ${\rho }_v^i$ drawn by $v$ throughout the protocol; (2) the labels ${\mu }_v^i$ assigned to $v$ by the prover throughout the protocol; and (3) the labels ${\mu }_u^i$ assigned to $v$’s neighbors $u\in N(v)$ by the prover throughout the protocol. We say that the verifier accepts the instance if all nodes output “yes”, and that the verifier rejects the instance if at least one node outputs “no”.

As standard, the correctness of a proof system is defined by completeness and soundness requirements. The completeness requirements asks that if $G\in {ℱ}_Y$, then there exists an honest prover causing the verifier to accept the instance; whereas the soundness requirement asks that if $G\in {ℱ}_N$, then for any prover, the verifier rejects the instance. In the DIP setting, the correctness requirements are relaxed so that the completeness and soundness hold with probabilities $1-{ϵ}_c$ and $1-{ϵ}_s$, respectively, for some parameters . In this case, we refer to ${ϵ}_c$ as the completeness error and to ${ϵ}_s$ as the soundness error. A protocol is said to have perfect completeness if ${ϵ}_c=0$. The performance of a DIP protocol is measured by the amount of prover-verifier communication it requires. Namely, the objective is to design protocols with a small number of interaction rounds and a small proof size which is defined as the size of the longest label assigned by the honest prover during the protocol.

As observed in [21], achieving sub-logarithmic proof lengths presents a significant challenge in the DIP setting and also serves as a lower bound for numerous problems in the non-interactive setting. This difficulty arises because many fundamental operations – such as identifying neighboring nodes, counting, or specifying node IDs – intrinsically require $\log n$ bits. While [21] made important initial progress in this area, their results apply to a more permissive variant of the DIP model, where nodes are allowed to send different messages to each of their neighbors. Indeed, their key technique is based on a rooted spanning tree provided by the prover such that every node identifies its tree-parent based on its internal port-numbering. Therefore, for each node to be able to learn its children in the tree (which is crucial to their protocols), every node has to send a distinct message to its parent.

In contrast, our work operates within the more restrictive DIP framework defined by Kol et al. [19], where nodes may only forward the proofs they receive to their neighbors. This constraint aligns with the non-interactive proof labeling model introduced in [20], where a node’s decision is based solely on its own proof and those of its neighbors. This key difference in model assumptions becomes especially important in the sub-logarithmic setting, effectively preventing us from directly applying the techniques developed in [21].

We present new distributed interactive proofs for various well-studied graph families. The first graph family considered is that of path-outerplanar graphs (see Section 2 for definition). Previously, [6] showed that path-outerplanarity admits a proof labeling scheme with a proof size of $O(\log n)$. We improve upon the communication complexity of that result by designing a protocol with exponentially shorter proof labels as specified in the following theorem.

Building upon the path-outerplanarity protocol, we provide a protocol for (general) outerplanarity with the same asymptotic communication guarantees.

We then move on to consider the case of planar graphs. In this context, we consider two verification tasks referred to as planar embedding and planarity. In the planar embedding task, an embedding of the graph is given in a distributed manner and the goal is to decide if it is a valid planar embedding (i.e., if no edges cross). In the planarity task, the goal is simply to decide if the given graph is planar. The details of our protocols for these tasks are given in the following two theorems.

We also consider the two closely related graph families of series-parallel graphs and graphs of treewidth at most $2$. We obtain the following two results.

Finally, we provide the following lower bound.

We note that Theorem 1.8 strengthens the lower bound presented in [6] in the following ways. First, the lower bound of [6] only applies to one-round proofs with deterministic verifier. Theorem 1.8 states that the same bound holds even if the verifier is randomized. Combined with the upper bounds stated above, our results present a strong evidence of the power added from interaction in the context of distributed proofs for planarity and related tasks. We remark that our lower bound holds even if the nodes have access to (unbounded) shared randomness. We also note that the lower bound of [6] does not explicitly apply to some of the graph families that appear in Theorem 1.8 (namely, path-outerplanar graphs, embedded planar graphs, and series-parallel graphs).

Our results leave some intriguing unresolved questions that can be explored in follow-up works. Here, we highlight three of them.

As the main open problem, we ask whether the additive $O(\log \mathrm{\Delta })$ term is necessary in the proof size for planarity. That is, we pose the following question.

One may also ask whether $5$ interaction rounds are necessary in order to obtain a proof size of $O(\log \log n)$ for the tasks discussed in this paper. Of course, we know by Theorem 1.8 that $1$ round is insufficient. However, for any , whether an $r$-round protocol exists remains open even if we simply look for a proof size of $o(\log n)$. This leads to the following open problem.

Finally, we ask whether it is possible to improve our protocol’s communication bound.

Throughout, if not specified otherwise, a graph $G=(V,E)$ is assumed to be undirected and connected. For each node $v\in V$, we stick to the convention that $N_G(v)$ denotes the set of $v$’s neighbors in the graph, $E(v)$ denotes the set of edges incident on $v$, and ${\mathrm{deg}}_G(v)=|N_G(v)|=|E(v)|$ denotes $v$’s degree in $G$. Whenever $G$ is clear from the context, we may omit it from the notation and write $N(v)$ and $\mathrm{deg}(v)$ instead of $N_G(v)$ and ${\mathrm{deg}}_G(v)$. For a node-subset $V^{\prime }\subseteq V$, we denote by $G(V^{\prime })$ the subgraph induced on $G$ by $V^{\prime }$.

As part of our technical tools, we also consider directed graphs. If $G$ is directed, we assume that the edge orientation is given to the nodes such that each node $v\in V$ can distinguish between its incoming and outgoing incident edges. For a directed edge $e$ with endpoints $u$ and $v$, we write $e=(u,v)$ to reflect that $e$ is directed from $u$ to $v$, and $e=(v,u)$ otherwise. In the context of a distributed interactive proof, we assume that the label assigned by the prover to node $v\in V$ can be viewed by both its incoming and outgoing neighbors.

Consider a graph $G=(V,E)$ with a Hamiltonian path $P$. For a pair $u,v\in V$ of nodes, define the relation ${\prec }_P$ so that $u{\prec }_{P}v$ if $u$ precedes $v$ in $P$. Naturally, this extends to $u{⪯}_{P}v$ if $u{\prec }_{P}v$ or $u=v$. Going forward, when $P$ is clear from context, we may omit it from our notation and write $u\prec v$ and $u⪯v$ instead of $u{\prec }_{P}v$ and $u{⪯}_{P}v$, respectively. Whenever we encounter a Hamiltonian path, it will be convenient to think of it drawn as a straight line from left to right. Keeping up with this convention, for each node $v\in V$, we can partition its non-path edges in $G$ into $v$-left edges which are incident on neighbors $u\prec v$, and $v$-right edges which are incident on neighbors $v\prec u$. We say that a non-path edge $(u,v)$ is the longest $v$-left (resp., $v$-right) edge if $u\prec v$ (resp., $v\prec u$) and $u\prec u^{\prime }$ (resp., $u^{\prime }\prec u$) for every neighbor $u^{\prime }\in N(v)$.

We define a verification task called left-right sorting (LR-sorting) which is used as a sub-task in our protocols. In LR-sorting, a directed graph $G=(V,E)$ is given. The graph $G$ admits a directed Hamiltonian path $P$ which is given such that each node $v\in V$ knows its incident edges in $P$. The path $P$ is assumed to be directed from left to right. The goal of the task is to decide if $u\prec v$ for every directed edge $(u,v)\in E-P$. That is, a yes-instance is defined so that $u\prec v$ for every edge $(u,v)\in E$; whereas a no-instance admits at least one edge $(u,v)\in E$ such that $v\prec u$. Observe that equivalently, yes-instances are ones in which $G$ is a DAG (in which case the $P$-ordering is the unique topological sort of $G$); and no-instances are ones in which $G$ admits some cycle.

A graph $G=(V,E)$ is said to be path-outerplanar if it admits a Hamiltonian path $P$ such that all non-path edges can be drawn above $P$ without crossings. If the edges can be drawn in such a manner, we say that they are properly nested within $P$ (or simply properly nested when $P$ is clear from the context). Equivalently, a graph is path-outerplanar if no two edges $(u,v),(u^{\prime },v^{\prime })\in E$ satisfy $u{\prec }_P{u}^{\prime }{\prec }_{P}v{\prec }_P{v}^{\prime }$ with respect to some Hamiltonian path $P$ (cf. [6]). Refer to Figure 1 for a pictorial example of a path-outerplanar graph and some of the related definitions.

The following simple observation will be useful in our protocol for path-outerplanar graphs in Section B.

Assume that $(u,v)$ is neither the longest $u$-right edge nor the longest $v$-left edge. Let $(u,v^{\prime })$ and $(u^{\prime },v)$ be the longest $u$-right and $v$-left edges, respectively. These edges satisfy $u^{\prime }\prec u\prec v\prec v^{\prime }$ which contradicts path-outerplanarity. $◀$

Given a path-outerplanar graph $G$, we make the following definitions. For a non-path edge $(u,v)$, $u\prec v$, define its successor as the edge $(u^{\prime },v^{\prime })$ that satisfies: (1) $u^{\prime }⪯u\prec v⪯v^{\prime }$; and (2) $u^{\prime \prime }⪯u^{\prime }\prec v^{\prime }⪯v^{\prime \prime }$ for every edge $(u^{\prime \prime },v^{\prime \prime })$ that satisfies $u^{\prime \prime }⪯u\prec v⪯v^{\prime \prime }$. Intuitively, the successor of an edge is the edge drawn directly above it. For cohesiveness, for any edge $e$ that does not have a successor in the graph, define the successor to be a virtual edge $e^{\ast }=(u^{\ast },v^{\ast }),u^{\ast },v^{\ast }\notin V$, defined so that $u^{\ast }\prec v\prec v^{\ast }$ for any $v\in V$. Notice that each edge has a unique successor. Naturally, we say that $e$ is a predecessor of $e^{\prime }$ if $e^{\prime }$ is the successor of $e$. We say that two edges $e$ and $e^{\prime }$ are siblings if they have a common successor.

The following observation is now straightforward from the definitions.

As a building block in our protocol, we would like for the prover to be able to communicate a spanning forest $F$ of the graph $G$ to the verifier. While it is trivial to achieve in general using $O(\log n)$-bit labels, in our case we would like much smaller labels. It turns out that this task can be achieved in planar graphs deterministically and with constant-sized labels. This is done by slightly extending a construction of [3] which is designed for the task of deciding whether a planar graph admits a perfect matching.⁴⁴4The scheme extends to some classes of non-planar graphs; see [3] for full details. We state the construction’s properties in the following lemma.

For completeness of presentation, we provide a proof for the lemma. We emphasize that this construction only allows the prover to communicate the forest $F$ to the verifier and does not provide proof that $F$ is indeed a spanning forest.⁵⁵5Another way to formulate this construction is in terms of advice, based on the model of [9, 10]. Specifically, using the terminology of [10], the statement means that computing any spanning forest of a planar graph admits an $(O(1),0)$-advising scheme.

For ease of presentation, let us assume that the prover tries to communicate a spanning tree $T$ (i.e., a connected forest). The case of an unconnected forest admits a similar construction. Suppose that $G=(V,E)$ is a planar graph and $T$ is a spanning tree rooted at some node $r\in V$. For each node $v\in V-\{r\}$, let $\text{parent}(v)$ denote its parent and let $0pt(v)$ denote its depth. Define the graph $G_{odd}$ (resp., $G_{even}$) to be the graph obtained by starting from $G$ and contracting all edges $(v,\text{parent}(v))$ that go from an odd (resp., even) depth node $v$ to its parent in $T$. Observe that $G_{odd}$ and $G_{even}$ are both planar and thus, $4$-colorable. Towards providing the label assignment, the prover computes $4$-colorings of $G_{odd}$ and $G_{even}$, respectively. For each node $v\in V$, let $c_1(v)$ the color of the node into which $v$ contracted in $G_{odd}$ and let $c_2(v)$ be the color of the node into which $v$ contracted in $G_{even}$. The prover assigns each node $v\in V$ with the label $L(v)=(c_1(v),c_2(v),\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v))$ where $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v)=0pt(v)mod2$.

We argue that the label assignment allows each node $v\in V$ to deduce which of its neighbors are its parent and children in $T$. The idea is as follows. If a node $v\in V$ of odd depth receives a color $c_1(v)$, then due to the validity of the coloring on $G_{odd}$, it holds that $\text{parent}(v)$ is the only neighbor of $v$ with even depth for which $c_1(\text{parent}(v))=c_1(v)$. The case of even depth nodes is similar.

To make things more concrete, consider some node $v\in V$ with $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v)=1$ (resp., $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v)=0$). Node $v$ identifies its parent as its only neighbor $u\in N(v)$ with $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(u)=0$ and $c_1(v)=c_1(u)$ (resp., $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v)=1$ and $c_2(v)=c_2(u)$). Additionally, $v$ identifies its children as the neighbors $u\in N(v)$ that satisfy $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(u)=0$ and $c_2(v)=c_2(u)$ (resp., $\mathrm{𝚙𝚊𝚛𝚒𝚝𝚢}(v)=1$ and $c_1(v)=c_1(u)$). $◀$

In the technical sections, it will be convenient to describe protocols assuming that the prover can also assign edge-labels (such that both of the edge endpoints can see the label) rather than only node-labels. This assumption is facilitated by the following lemma.⁶⁶6Transformations that enable edge-labels in planar graphs have been presented in previous papers (see, e.g., [6]). However, these constructions require the prover to assign an ordering to the nodes which incurs an additive $\mathrm{\Theta }(\log n)$ overhead to the label size. Thus, we cannot use these transformations for our purposes.

It is well-known that planar graphs have arboricity at most $3$. This means that the edge-set of any planar graph $G=(V,E)$ can be partitioned into three edge-disjoint forests $F_1,F_2,F_3$. By Lemma 2.3, the prover can inform each node $v\in V$ of its parent and children in each $F_i$ using only constant-sized labels. Then, instead of assigning a label $L(u_i,v)$ to the edge $(u_i,v)$ between $v$ and its parent $u_i$ in $F_i$, the prover simply writes $L(u_i,v)$ to a field in $v$’s label which is designated for its parent in $F_i$. This allows both endpoints to learn the label $L(u_i,v)$, thus enabling the simulation of edge-labels. $◀$

Consider a graph $G=(V,E)$ and let $T$ be a subgraph of $G$ such that each node $v\in V$ knows its incident edges in $T$. We define spanning tree verification as the task of deciding whether $T$ is a spanning tree of $G$. The following lemma is established in [21].

Observe that by standard parallel repetition, one can reduce the soundness error to $1/2^{\mathrm{\ell }}$ at the expense of a $\mathrm{\Theta }(\mathrm{\ell })$ proof size for any parameter $\mathrm{\ell }>0$. Throughout the paper, this fact will be used in a black-box manner.

In the multiset equality problem, each node $v\in V$ receives as input two multisets $S_1(v),S_2(v)$ and the goal is to decide whether $S_1=S_2$, where $S_1$ and $S_2$ are the multisets $S_1={\bigcup }_{v\in V}{S}_1(v)$ and $S_2={\bigcup }_{v\in V}{S}_2(v)$. Notice that in the definition of $S_1$ and $S_2$, the union is taken with respect to multisets, i.e., the multiplicity of element $s$ in $S_1$ (resp., $S_2$) is the sum of its multiplicities over all multisets $S_1(v)$ (resp., $S_2(v)$). The multisets $S_1$ and $S_2$ are assumed to be of size at most $k$ for some integer $k>0$, and the elements are taken from a universe of size $k^c$ for some constant $c\ge 1$. For our purposes, it would also be convenient to assume that the nodes are given a distributed encoding of a rooted spanning tree of the graph. The following lemma can be derived from the multiset equality protocol of [21].

Since the lemma above is not explicit in [21] and since we use the details of the multiset equality protocol in a white-box manner, we describe here the construction’s details. The multiset equality protocol relies on the following idea. For a multiset $S$, define the polynomial ${\phi }_S(x)={\prod }_{s\in S}(s-x)$.⁷⁷7Notice that we assume here w.l.o.g. that multiset elements are integers. Now, observe that $S_1=S_2$ if and only if ${\phi }_{S_1}\equiv {\phi }_{S_2}$. Moreover, notice that the degree of ${\phi }_{S_1}(x)$ and ${\phi }_{S_2}(x)$ is at most $k$. Define $p$ as the smallest prime number that satisfies $p>k^{c+1}$ and let $z$ be a variable drawn uniformly at random from $\{0,\mathrm{\dots },p-1\}$. By polynomial identity testing properties, if ${\phi }_{S_1}\not\equiv {\phi }_{S_2}$ and ${\phi }_{S_1}(z),{\phi }_{S_2}(z)$ are computed over the field ${𝔽}_p$, then $\mathrm{Pr}[{\phi }_{S_1}(z)={\phi }_{S_2}(z)]\le k/p\le 1/k^c$.⁸⁸8Recall that ${𝔽}_p$ is the field whose elements are $\{0,\mathrm{\dots },p-1\}$ and operations are done modulo $p$.

Following this idea, the multiset equality problem essentially reduces to evaluating a polynomial at a random point $z\in \{0,\mathrm{\dots },p-1\}$. Recalling that we assume that a distributed encoding of a rooted spanning tree is provided to the nodes, the polynomial evaluation is implemented as follows. First, the point $z\in \{0,\mathrm{\dots },p-1\}$ is sampled by the root and sent to the prover. Then, the prover assigns each node $v\in V$ with the value $z$ and the values ${\phi }_{S_1^v}(z),{\phi }_{S_2^v}(z)$ (computed over ${𝔽}_p$) where $S_1^v$ (resp., $S_2^v$) is the multiset of elements from $S_1$ (resp., $S_2$) in $v$’s subtree. Given the assigned values, it is well-known that their validity can be checked at each node $v\in V$ based on its input, its label, and its children’s labels. This is because polynomial evaluation is an aggregation task that can be verified “up the tree” (see, e.g., [20, Lemma 4.4] for details). Following these checks, the root $r$ can check that ${\phi }_{S_1^r}(z)={\phi }_{S_2^r}(z)$ (which implies that ${\phi }_{S_1}(z)={\phi }_{S_2}(z)$).

To summarize, given a rooted spanning tree of the graph, the multiset equality protocol runs for $2$ interaction rounds, admits perfect completeness, a soundness error of $1/k^c$, and a proof size of $O(\log p)=O(\log k)$.⁹⁹9Recall that standard density of primes properties assure that $p$ cannot be too large. In particular, , and thus $\log p=O(\log k)$.

To give an intuition for the LR-sorting protocol, let us first sketch a simple one-round protocol for LR-sorting with a proof size of $O(\log n)$. The prover assigns each node with its position on the path. Then, each node $v\in V$ that is located at the $i$-th position can verify that: (1) its path-neighbors are located at positions $i\pm 1$; and (2) all of its outgoing edges go towards nodes of larger positions.

To obtain a distributed interactive proof with a proof size of $O(\log \log n)$, the idea is to divide the nodes into node-disjoint blocks where each block is made up of $\lceil \log n\rceil$ consecutive path-nodes. This allows the prover to distribute the position of block $b$, denoted by $\mathrm{𝚙𝚘𝚜}(b)$, such that each node receives: (1) its index $i\in [\lceil \log n\rceil ]$ within $b$; and (2) $\mathrm{𝚙𝚘𝚜}(b)[i]$, i.e., the $i$-th most significant bit of $b$’s position. Ideally, as in the clustering approach, we would like for each block to act as a single node in the trivial protocol. In this short description, let us assume for simplicity that the prover encodes the position of the blocks correctly according to the $P$-ordering and let $\mathrm{𝚙𝚘𝚜}(b)$ denote the position of block $b$. The main challenge of the protocol is then captured by the following question: suppose that there is an edge $(u,v)$ where $u$ and $v$ belong to different blocks $b_u,b_v$, how can the prover prove to $u$ and $v$ that ?

Towards answering this question, let us first consider the simpler case where $(u,v)$ is the only edge leaving the block for both $b_u$ and $b_v$. Furthermore, we will describe the protocol under the assumption that the prover can assign edge-labels. Recall that Lemma 2.4 implies that the edge-labels assumption can be simulated in planar graphs while incurring only a constant overhead to the proof size. Let $i$ be the index of the most significant bit in which $\mathrm{𝚙𝚘𝚜}(b_u)$ and $\mathrm{𝚙𝚘𝚜}(b_v)$ differ. Notice that by definition, if , then $\mathrm{𝚙𝚘𝚜}(b_u)[i]=0$ and $\mathrm{𝚙𝚘𝚜}(b_v)[i]=1$. In addition, $i$ is in the range $[\lceil \log n\rceil ]$ and thus, can be encoded using $O(\log \log n)$ bits. In the first interaction, the prover encodes $i$ to the label of $(u,v)$. The prover then needs to prove that (1) $\mathrm{𝚙𝚘𝚜}(b_u)[i]=0$; (2) $\mathrm{𝚙𝚘𝚜}(b_v)[i]=1$; and (3) $\mathrm{𝚙𝚘𝚜}(b_u)$ and $\mathrm{𝚙𝚘𝚜}(b_v)$ agree on their $i-1$ most significant bits.

Let us focus on how (3) is proved. A straightforward way to obtain a proof for (3) is to assign the edge $(u,v)$ with the substring containing the $i-1$ most significant bits in their blocks. The main problem with this approach is that the proof size could be as large as $\mathrm{\Theta }(\log n)$. To avoid this large label size, we can use polynomial identity testing. That is, we interpret the substrings containing the $i-1$ most significant bits in $\mathrm{𝚙𝚘𝚜}(b_u)$ and $\mathrm{𝚙𝚘𝚜}(b_v)$ as polynomials of degree $O(\log n)$ and seek to have the prover and verifier evaluate them at a random point over a field of size $\text{poly}\log n$. The prover then assigns the outcome of the polynomial evaluation to the label of $(u,v)$. This introduces the following locality problem: the verification that the polynomials were computed correctly is done at the $(i-1)$-th leftmost node in each block (using the standard aggregation technique of [20]). Since $u$ and $v$ might be far from the $(i-1)$-th leftmost node in their respective blocks, they cannot locally detect that the prover is not lying about the outcome. We note that in the simplified case where $(u,v)$ is the only edge leaving $b_u$ and $b_v$, the problem is easy to solve. Indeed, since $(u,v)$ is the only edge considered by blocks $b_u$ and $b_v$, the prover can assign the outcome of the polynomial evaluation at the $(i-1)$-th node to all nodes of $b_u$ and $b_v$. The nodes can then check the correctness of this assignment locally based on the assignment to their block-neighbors.

Moving on to the general case where each block may have many edges leaving it, it is not clear how to solve the locality problem described above. Of course, if the prover assigns each node of the block with the outcomes of polynomial evaluations for every relevant index, this could require assigning $\mathrm{\Theta }(\log n)$ values to every node which completely defeats the purpose. The main observation that we make is that one can formulate the locality problem as an instance of multiset equality between two multisets that are carefully defined within each block. Then, to check whether the multisets are indeed equal, a multiset equality protocol is executed within the blocks. An important property of the constructed multisets is that they are of size $\text{poly}\log n$ which means that this final step can be done while maintaining a proof size of $O(\log \log n)$.

For the correctness, it turns out that the protocol’s completeness becomes straightforward from the multisets construction, whereas the soundness argument requires a bit more care. Essentially, we show that in a no-instance the prover is likely to commit to a pair of unequal multisets within some block. Then, conditioning on this event, it is likely that the verifier rejects the instance due to the soundness of the multiset equality protocol.

In Section B, we devise a protocol for path-outerplanarity. To get intuition of how the protocol works, we first recall the labels assigned in the non-interactive proof of [6]. Essentially, the prover assigns each node $v\in V$ with its position in the path $P$ along with the position of the nodes $u$ and $u^{\prime }$ for which $(u,u^{\prime })\in E$ is the first edge that is drawn above $v$. The authors of [6] show that this labeling allows the (deterministic) verifier to verify that indeed $G$ is path-outerplanar.

Of course, assigning the positions of nodes in $P$ is far too costly for our purposes, so we seek to avoid it by using interaction and randomization. To that end, we first note that the assignment of positions in [6] serves the following purposes: (1) each node learns its $P$-neighbors; (2) each edge can be identified based on the positions of its endpoints; and (3) each node learns a clockwise orientation of its incident edges. Note that since $P$ is a spanning tree, (1) can be obtained using only constant-sized labels based on Lemmas 2.3 and 2.5. For (2), we show that the edge identifiers can be replaced by random bits. As for (3), we design a protocol in which it is sufficient for every node to only distinguish between its left and right edges with respect to the path $P$. In fact, we show that under the assumption that every node knows its left and right edges, path-outerplanarity can be solved in $3$ rounds and with a constant proof size (refer to Lemma B.1 for the full details of the reduction). To lift this assumption, we can apply our LR-sorting protocol which leads to the stated complexity bound of Theorem 1.2.

We handle outerplanarity and planarity through reductions to path-outerplanarity. We note that while such reductions are presented in previous works ([6] for planarity; [2] for outerplanarity), we cannot use them as-is in our setting. This is because these reductions incur an additive $\mathrm{\Theta }(\log n)$ overhead to the proof size. Nevertheless, our results rely on some modifications of the existing reductions. For outerplanarity, our reduction is white-box and it avoids the $\mathrm{\Theta }(\log n)$ overhead based on the tools of Lemma 2.3 and Lemma 2.5 as well as some observations regarding the path-outerplanarity protocol.

For planarity, we start from the planar embedding task as an intermediate point. To reduce planar embedding to path-outerplanarity, we revisit some of the constructive proofs presented in [6] and show that they can be used to obtain such a reduction. Once again, Lemma 2.3 and Lemma 2.5 are used for the sake of efficient implementation. Then, we show that planarity reduces to planar embedding while incurring only an additive $O(\log \mathrm{\Delta })$ overhead to the proof size, thus obtaining the stated result.

The starting point for our lower bounds is the lower bound of [6] which applies to proof labeling schemes (in fact, it holds also for the more general locally checkable proofs [16]). The result of [6] shows that an $\mathrm{\Omega }(\log n)$ proof size is required even for the task of deciding whether a graph is outerplanar or non-planar. We start by adjusting the lower bound’s details so that it would apply for the task of deciding whether a graph is biconnected outerplanar or non-planar.¹¹¹¹11Recall that a graph is biconnected if the removal of any node leaves the resulting graph connected. A biconnected component of a graph $G$ is a maximal biconnected subgraph of $G$. This adjustment leads to a bound for all the graph families considered in the current paper since they are planar and contain all biconnected outerplanar graphs. To extend the lower bound to one-round protocols in which the verifier is randomized, we use a framework presented in [11].