# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## Appendix A Graph Families with Good Separators  
In the following, we present a brief summary of graph families that allow for good separator and that are closed under partitioning, i.e., each element of the partition is within the class. **Planar Graphs. ** A graph that can be drawn without edge crossings is called _planar_[49]. This type of graphs arises typically in applications related to 2-D meshes and computer graphics. For such graphs the following separator theorem is known:  
**Theorem A1** ([28]). : _Planar graphs satisfy a \(\mathcal{O}(n^{1/2})\)-separator theorem with constant \(\alpha=2/3\) and \(\beta=2\sqrt{2}\)._  
In addition, [PERSON] and [PERSON] also provided a linear-time algorithm to find such a separator in planar graphs. This result is of great importance as for large-scale graphs the computation of such partition remains feasible. Besides planar graphs, degenerate instances of them such as edgeless graphs, linked lists, and trees have good vertex separators [50; 51; 52]. **Almost Planar Graphs. ** Similar to planar graphs, almost planar graphs can be made planar by solely removing a small number of edges. Instances of this kind of graphs are road networks or power grids. In such (physical) networks, planarity is lost by bridges or tunnels, therefore by removing such edges, the graph can be approximated through a planar one. As a result, the \(\mathcal{O}(n^{1/2})\)-separator theorem for planar graphs holds (approximately) for this family of graphs. **Finite Element Graphs. ** This family of graphs arises from finite element methods, for example through a tessellation of the space. Following the formal description of [PERSON], et al. a finite element graph can be obtained from a planar graph as follows. First, the graph is embedded in a plane. Next, we identify certain points as _nodes_, e.g., vertices, points on edges, points in faces. Then, edges between all nodes that share a face are _drawn_. From this construction, if the number of nodes per face is bounded by \(d\), finite elements graphs satisfy a \(\mathcal{O}(dn^{1/2})\)-separator theorem [28]. **Graphs Embedded in a Low-Dimensional Space. ** Interestingly enough, nearly all graphs that are used to represent connections in low dimensional spaces have small separators. For example, 3-D meshes, under certain nicety conditions, accept a \(\mathcal{O}(n^{2/3})\)-separator theorem [53]. In general, _unstructured meshes_ of dimension \(d\) allow a \(\mathcal{O}(n^{(d-1)/d})\)-separator theorem [53]. **Circuits. ** These are one of the families of graphs that motivated the early application of graph separators. This class and its separator are still used for VLSI design when designers want to minimize the area employed [54]. If the circuit, represented through vertices (components) and edges (connections) is drawn with _few_ crossings, then it may be considered as an almost planar graph. Hence, the \(\mathcal{O}(n^{1/2})\)-separator theorem approximately holds. Otherwise, if the circuit can be embedded on a surface of genus [9]\(g\), then it has an exact \(\mathcal{O}((gn)^{1/2})\)-separator theorem [51]. **Geometric Graphs. ** This family of graphs arises by construction through _geometrical objects_. As this family of graphs encloses a large variety of objects, e.g., k-nearest-neighbor graphs, meshes, etc., here we only consider the _unit disk_ graphs subfamily. Unit disk graphs arise naturally in applications involving sensors networks. These graphs are combinatorial objects generated by the intersection of disks on the plane. They are also known as _Euclidean_ graphs. These graphs are constructed from points in the space (vertices) when edges between points are drawn if the distance between them is smaller than some threshold, e.g., range-limit communication graph. For this family of graphs, a \(\mathcal{O}(n^{1/2})\)-separator theorem holds similarly to the case of planar graphs as they are embeddable in a 2-D surface. For a more in-depth discussion of the results related to this kind of graphs, the reader is referred to [29].