7.4 Planarity Testing and Embedding
3 min read•august 12, 2024
Graph drawing and planarity are crucial in visualizing complex relationships. Planarity testing algorithms determine if a graph can be drawn without edge crossings, while planar techniques assign coordinates to vertices and edges.
Understanding obstructions helps identify non-planar graphs. , which states that a graph is planar if it contains no subdivisions of K5 or K3,3, is fundamental to characterizing planarity and developing efficient algorithms.
Planarity Testing Algorithms
Fundamentals of Planarity Testing
Top images from around the web for Fundamentals of Planarity Testing
Planarity and multiple components promote organic photovoltaic efficiency by improving ... View original
Is this image relevant?
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width | SpringerLink View original
Is this image relevant?
combinatorics - Planar graph with a chromatic number of 4 where all vertices have a degree of 4 ... View original
Is this image relevant?
Planarity and multiple components promote organic photovoltaic efficiency by improving ... View original
Is this image relevant?
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width | SpringerLink View original
Is this image relevant?
1 of 3
Top images from around the web for Fundamentals of Planarity Testing
Planarity and multiple components promote organic photovoltaic efficiency by improving ... View original
Is this image relevant?
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width | SpringerLink View original
Is this image relevant?
combinatorics - Planar graph with a chromatic number of 4 where all vertices have a degree of 4 ... View original
Is this image relevant?
Planarity and multiple components promote organic photovoltaic efficiency by improving ... View original
Is this image relevant?
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width | SpringerLink View original
Is this image relevant?
1 of 3
- Planarity testing determines if a graph can be drawn on a plane without edge crossings
- Linear-time algorithms efficiently test planarity with time complexity, where represents the number of vertices
- uses to identify planar graphs
- Decomposes the graph into biconnected components
- Recursively tests each component for planarity
- Combines results to determine overall graph planarity
- improves upon Hopcroft-Tarjan with simpler implementation
- Utilizes a left-right planarity test
- Maintains a partial embedding during the testing process
- Incrementally adds vertices while preserving planarity
Algorithmic Approaches and Implementations
- Depth-first search forms the basis for many planarity testing algorithms
- Edge addition techniques test planarity by incrementally adding edges
- Maintain a partial embedding at each step
- Check if new edges can be added without creating crossings
- Planarity testing algorithms often use data structures like or
- PQ-trees represent possible permutations of elements
- PC-trees maintain partial embeddings during the testing process
- Implementation considerations include:
- Efficient graph representation (adjacency lists)
- Careful handling of special cases (disconnected graphs)
- Optimization techniques to improve average-case performance
Planar Embedding Techniques
Constructing Planar Embeddings
- Planar embedding assigns coordinates to vertices and edges without crossings
- Edge addition techniques incrementally construct planar embeddings
- Start with a planar subgraph (often a spanning tree)
- Add remaining edges one by one, updating the embedding
- Utilize routing to find paths for new edges
- handle non-planar graphs
- Identify a maximal planar subgraph
- Add remaining edges, introducing crossings as needed
- Represent crossings as dummy vertices
Advanced Embedding Strategies
- Straight-line drawings embed planar graphs with straight edges
- guarantees existence for all planar graphs
- Algorithms like or construct such drawings
- Orthogonal drawings use only horizontal and vertical line segments
- Particularly useful for VLSI design and circuit layouts
- Algorithms like the produce compact orthogonal drawings
- create aesthetically pleasing embeddings
- Model edges as springs and vertices as charged particles
- Iteratively adjust vertex positions to minimize energy
- Can be adapted for planar graphs by adding planarity constraints
Planar Graph Obstructions
Characterizing Non-Planar Graphs
- Obstruction set consists of minimal non-planar graphs
- Removing any edge from an obstruction set graph results in a planar graph
- Key to understanding the structure of non-planar graphs
- refers to subdivisions of or
- represents the complete graph on 5 vertices
- is the complete bipartite graph with 3 vertices in each partition
- Kuratowski's theorem states a graph is planar if and only if it contains no Kuratowski subgraph
Detecting and Utilizing Obstructions
- Algorithms for finding Kuratowski subgraphs
- Often integrated into planarity testing algorithms
- Can provide a certificate of non-planarity
- Useful for explaining why a graph is not planar
- Applications of obstruction detection
- Graph minor theory utilizes obstruction sets
- Helps in understanding graph classes and their properties
- Guides the development of algorithms for graph problems
- Generalizations to other surfaces
- Obstruction sets exist for embeddings on higher-genus surfaces
- More complex than the planar case, with larger obstruction sets
- Active area of research in topological graph theory
Key Terms to Review (29)
Boyer-Myrvold Algorithm: The Boyer-Myrvold Algorithm is an efficient method for determining whether a given graph is planar, meaning it can be drawn on a plane without any edges crossing. This algorithm operates in linear time, specifically in O(n) complexity, which is significant because it allows for the rapid analysis of large graphs to assess their planarity and to find embeddings if they are indeed planar. Its utility is critical in applications where understanding the structure of graphs is essential, such as circuit design and geographical mapping.
Crossing Number: The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph in the plane. This concept is crucial for understanding how graphs can be represented visually and relates directly to planarity, which affects the way graphs can be interpreted and analyzed. The crossing number helps quantify the complexity of a graph's layout and is important in various applications, such as graph drawing algorithms and geometric representations of graphs.
Depth-first search: Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. It explores as far as possible along each branch before backtracking, making it particularly useful for planarity testing and embedding, where the goal is to explore the structure of a graph in a systematic way while determining if it can be drawn on a plane without edges crossing.
Dual graph: A dual graph is a graph that represents the relationships between the faces of another graph, where each vertex of the dual graph corresponds to a face of the original graph, and each edge represents the adjacency between two faces. This concept is crucial for understanding properties of planar graphs, as well as the relationship between Voronoi diagrams and Delaunay triangulations, where each structure can be seen as a dual of the other.
Edge connectivity: Edge connectivity is a measure of how well-connected a graph is, defined as the minimum number of edges that need to be removed to disconnect the graph. It reflects the resilience of a graph against edge failures and can be crucial in understanding the structure and robustness of networks. A higher edge connectivity indicates a more robust graph, where multiple edges exist between nodes, allowing for alternate paths even if some edges are removed.
Embedding: Embedding refers to the way a graph is drawn on a surface without any edges crossing each other, preserving the graph's structure. This concept is critical when analyzing planar graphs, as it not only defines how these graphs can be visually represented but also helps in understanding their properties and relationships with surfaces. An embedding of a graph shows how vertices and edges can be arranged in a two-dimensional space while ensuring that the connections remain intact and do not overlap.
Euler's Formula: Euler's Formula is a fundamental equation in geometry that relates the number of vertices (V), edges (E), and faces (F) of a convex polyhedron through the equation $$V - E + F = 2$$. This relationship highlights the intrinsic link between these geometric components and serves as a cornerstone in various branches of mathematics, particularly in discrete geometry and topology.
Face: In geometry, a face refers to any of the flat surfaces that make up a polytope. Faces can be two-dimensional shapes that form the boundaries of three-dimensional objects and play a critical role in understanding the structure and properties of polytopes. They can vary in shape and size, and the study of faces includes investigating how they relate to one another and contribute to the overall geometric characteristics.
Fáry's Theorem: Fáry's Theorem states that every planar graph can be represented as a straight-line drawing in the plane, where no two edges cross each other. This theorem is crucial for understanding how to visualize graphs in a way that maintains their structural integrity while ensuring clarity. It connects with various aspects of graph theory and provides a basis for creating clean visual representations, particularly in orthogonal and polyline drawings as well as during planarity testing and embedding processes.
Force-directed algorithms: Force-directed algorithms are a class of methods used in graph drawing that model the graph as a physical system, where vertices are represented as charged particles and edges as springs. The goal is to minimize energy in the system, leading to a visually appealing layout that effectively represents the relationships within the graph. These algorithms are particularly useful in producing planar embeddings and ensuring that vertices are spaced evenly without overlaps.
Homeomorphic Embedding: Homeomorphic embedding refers to a type of mapping between two topological spaces where one space can be transformed into another without tearing or gluing, preserving the structure of the objects involved. This concept is crucial when analyzing the planarity of graphs, as it helps determine if a graph can be drawn in a plane without edges crossing, maintaining the same connectivity properties.
Hopcroft-Tarjan Algorithm: The Hopcroft-Tarjan Algorithm is a highly efficient method used for testing the planarity of graphs and embedding them in the plane. This algorithm operates in linear time, specifically O(n), where n is the number of vertices, making it one of the fastest algorithms for checking if a graph can be drawn without edge crossings. Its capability to find a planar embedding is critical in fields such as computer graphics and geographical information systems.
Kuratowski subgraph: A kuratowski subgraph is a specific type of subgraph that arises in the context of planarity testing, defined as either a subdivision of the complete graph $K_5$ or a subdivision of the complete bipartite graph $K_{3,3}$. These two graphs are crucial in determining whether a given graph can be drawn on a plane without any edges crossing. Identifying these subgraphs helps in understanding the limitations of graph embeddings and the conditions under which a graph is non-planar.
Kuratowski's Theorem: Kuratowski's Theorem states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph $K_5$ (five vertices, all connected) or the complete bipartite graph $K_{3,3}$ (two sets of three vertices, each connected to every vertex in the other set). This theorem serves as a foundational principle in understanding planar graphs, connecting geometric properties with topological structures.
Non-planar graph: A non-planar graph is a type of graph that cannot be drawn on a flat plane without edges crossing. This means that no matter how you arrange the vertices and edges, at least one pair of edges will overlap in a way that violates the rules of planar graphs. Non-planar graphs often have complex structures and are significant in understanding certain properties and behaviors in geometric graph theory as well as in planarity testing and embedding.
Orthogonal Drawing: An orthogonal drawing is a way of representing a graph in a two-dimensional space where all edges are drawn as sequences of horizontal and vertical line segments. This type of drawing emphasizes clear visual representation and can be particularly useful for understanding complex structures, especially in the context of planarity and embedding where clarity and organization of spatial relationships are crucial.
Pc-trees: Pc-trees, or planar contact trees, are data structures used to represent planar graphs in a way that helps efficiently determine their planarity and embeddings. They serve as a bridge between combinatorial properties of graphs and geometric realizations, allowing for efficient algorithms to assess how a graph can be embedded in the plane without edges crossing. The structure highlights relationships between vertices while ensuring that adjacency is preserved in a planar context.
Planar Graph: A planar graph is a graph that can be drawn on a plane without any edges crossing each other. This concept is crucial as it connects various mathematical principles, like Euler's formula, which relates the number of vertices, edges, and faces in a connected planar graph. Understanding planar graphs also involves techniques for testing their planarity and finding embeddings, as well as applications in polygon triangulation for efficient computational geometry.
Planarization methods: Planarization methods are techniques used to transform a non-planar graph into a planar graph, enabling it to be drawn on a plane without edge crossings. These methods are essential for graph embedding, as they help identify and resolve issues of planarity, allowing for better visualization and analysis of the graph's structure. By applying these methods, one can determine how to adjust the graph while maintaining its essential properties.
Pq-trees: A pq-tree is a data structure that represents permutations of a set of elements, allowing for efficient testing of certain properties like planarity and embedding of graphs. It encodes the allowed orderings of a set of vertices based on their relationships, which is crucial for determining whether a graph can be drawn in a planar way without edge crossings.
Proper embedding: Proper embedding refers to the representation of a graph in the plane such that no edges intersect except at their endpoints. This concept is crucial for visualizing graphs clearly without any confusion caused by edge crossings, ensuring that each vertex is represented by a distinct point in the plane. Proper embeddings help in determining the planarity of a graph, which indicates whether it can be drawn on a flat surface without overlaps.
Schnyder Woods: Schnyder Woods are a specific representation of planar graphs that provide a way to visualize how a planar graph can be embedded in the plane without edge crossings. This concept is pivotal in planarity testing and embedding, as it enables an efficient method to create a planar drawing while maintaining the structure of the graph.
Sphere: A sphere is a perfectly symmetrical three-dimensional shape where every point on its surface is equidistant from a fixed center point. This concept of uniform distance relates to various applications in discrete geometry, particularly in planarity testing and embedding, where understanding the structure and representation of shapes is essential.
Straight-line drawing: A straight-line drawing is a geometric representation of a graph where each vertex is represented by a point and each edge is represented by a straight line segment connecting the corresponding points. This concept is essential for visualizing graphs in a clear and concise manner, allowing for easy interpretation of relationships between vertices. When discussing graph theory, the ability to create straight-line drawings aids in planarity testing and embedding, helping to determine if a graph can be drawn on a plane without edges crossing.
Subdivision: Subdivision refers to the process of dividing a geometric shape or space into smaller, simpler components, often to analyze or represent complex structures. In the context of planarity testing and embedding, subdivision plays a crucial role in determining whether a graph can be drawn on a plane without edge crossings, and it helps in the visualization of complex topological features.
Topology-shape-metrics approach: The topology-shape-metrics approach is a framework used to analyze and classify geometric structures by considering their topological properties, shapes, and associated metrics. This method helps in understanding the intrinsic characteristics of geometric objects, making it easier to determine their planarity and potential embeddings in various dimensions. It effectively combines the study of connectivity and continuity in geometry with quantitative measurements, allowing for a comprehensive examination of spatial relations and structures.
Torus: A torus is a doughnut-shaped surface that is formed by rotating a circle around an axis that does not intersect the circle. It has unique properties in topology, particularly concerning its planarity and embeddings in three-dimensional space. The torus is essential for understanding complex surfaces and their behavior in relation to graph theory and geometric structures.
Tutte Embedding: A Tutte embedding is a way to represent a planar graph in the Euclidean plane such that the vertices are placed at specific points and the edges do not cross each other. This concept is significant because it allows for the visualization of planar graphs while preserving their combinatorial properties, making it a vital technique in planarity testing and embedding discussions.
Vertex Connectivity: Vertex connectivity refers to the minimum number of vertices that need to be removed from a graph in order to disconnect it or make it trivial (having only one vertex). This concept is crucial for understanding how robust a graph is against vertex failures, which is important in various applications like network design and reliability. Vertex connectivity helps in analyzing the structure of graphs in terms of their resilience and also plays a role in planarity, as certain connectivity characteristics affect the way graphs can be drawn without intersections.