About the Book
Please note that the content of this book primarily consists of articles available from Wikipedia or other free sources online. Pages: 68. Chapters: Geometric graphs, Planar graphs, Four color theorem, Delaunay triangulation, Tait's conjecture, Graph drawing, Planar separator theorem, Apex graph, Pseudotriangle, Circle packing theorem, Beta skeleton, Periodic graph, Outerplanar graph, Euclidean minimum spanning tree, Steinitz's theorem, FKT algorithm, Steiner tree problem, Circle graph, Fary's theorem, Vietoris-Rips complex, SPQR tree, Planarity testing, Interval graph, Unit distance graph, Barnette's conjecture, Hadwiger-Nelson problem, Boxicity, Series-parallel graph, Scheinerman's conjecture, Cactus graph, Herschel graph, Relative neighborhood graph, Unit disk graph, Goldner-Harary graph, Circular-arc graph, Nearest neighbor graph, Halin graph, Durer graph, Grotzsch's theorem, Pitteway triangulation, Rectilinear Steiner tree, Visibility graph, Dual graph, Permutation graph, Squaregraph, Wheel graph, Matchstick graph, Geometric spanner, Friendship graph, Levi graph, Polyhedral graph, Bull graph, Frucht graph, Doubly-connected edge list, Erd s-Diophantine graph, Butterfly graph, Minimum-weight triangulation, Book, Laman graph, Schnyder's theorem, Urquhart graph, Bidiakis cube, Planar straight-line graph, Gabriel graph, Fraysseix-Rosenstiehl's planarity criterion, Ladder graph, Lattice graph, Yao graph, Rectilinear minimum spanning tree, Grinberg's theorem, Hanan grid, Visibility graph analysis, Constrained Delaunay triangulation, Mac Lane's planarity criterion. Excerpt: In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O( n) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 verti...
