Search

We introduce the problem Synchronized Planarity. Roughly speaking, its input is a loop-free multi-graph together with synchronization constraints that, e.g., match pairs of vertices of equal degree by providing a bijection between their edges. Synchronized Planarity then asks whether the graph admits a crossing-free embedding into the plane such that the orders of edges around synchronized vertices are consistent.We show, on the one hand, that Synchronized Planarity can be solved in quadratic time, and, on the other hand, that it serves as a powerfulmodeling language that lets us easily formulate several constrained planarity problems as instances of Synchronized Planarity. In particular, this lets us solve Clustered Planarity in quadratic time, where the most efficient previously known algorithm has an upper bound of O(n8). [ABSTRACT FROM AUTHOR]

We give a distributed algorithm in the CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (Proceedings of the 30th International Symposium on Distributed Computing, pp. 43–56, 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph G = (V , E) and a distance parameter ϵ , if G is planar, then every node outputs accept, and if G is ϵ -far from being planar (i.e., more than ϵ · | E | edges need to be removed in order to make G planar), then with probability 1 - 1 / poly (n) at least one node outputs reject. The algorithm runs in O (log | V | · poly (1 / ϵ)) rounds, and we show that this result is tight in terms of the dependence on |V|. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs. [ABSTRACT FROM AUTHOR]

We construct an optimal linear-time algorithm for the maximal planar subgraph problem: given a graph G′, find a planar subgraph G′ of G such that adding to G′ an extra edge of G results in a nonplanar graph. Our solution is based on a fast data structure for incremental planarity testing of triconnected graphs and a dynamic graph search procedure. Our algorithm can be transformed into a new optimal planarity testing algorithm. [ABSTRACT FROM AUTHOR]

We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be found in [MMN]. [ABSTRACT FROM AUTHOR]