📐Discrete Geometry Unit 7 – Graph Drawing and Planarity

Key Concepts and Definitions

• Graphs consist of vertices (nodes) connected by edges (lines or arcs)
  • Vertices represent objects or entities
  • Edges represent relationships or connections between vertices
• Directed graphs (digraphs) have edges with a specific direction indicated by arrows
• Undirected graphs have edges without any specific direction
• Weighted graphs assign values (weights) to edges representing costs, distances, or capacities
• Degree of a vertex is the number of edges incident to it
  • In-degree counts incoming edges, out-degree counts outgoing edges
• Complete graphs have an edge between every pair of vertices
• Bipartite graphs divide vertices into two disjoint sets with edges only between sets

Graph Representation Techniques

• Adjacency matrix uses a 2D array to represent graph connections
  • Matrix element

    A[i][j]

    is 1 if an edge exists from vertex

    i

    to

    j

    , 0 otherwise
  • Requires $O(V^2)$ space, where $V$ is the number of vertices
• Adjacency list uses an array of linked lists to store graph connections
  • Each vertex has a linked list of its adjacent vertices
  • Requires $O(V+E)$ space, where $E$ is the number of edges
• Edge list is a simple list of all edges in the graph
  • Each edge is represented as a pair of vertices

    (u, v)

  • Suitable for sparse graphs with few edges
• Incidence matrix represents the relationship between vertices and edges
  • Matrix element

    M[i][j]

    is 1 if vertex

    i

    is incident to edge

    j

    , 0 otherwise
• Choosing the right representation depends on the graph density and required operations

Planar Graphs and Their Properties

• Planar graphs can be drawn on a plane without any edge crossings
  • Edges may only intersect at their endpoints (vertices)
• Euler's formula relates the number of vertices ($V$), edges ($E$), and faces ($F$) in a connected planar graph: $V - E + F = 2$
• Kuratowski's theorem characterizes non-planar graphs by the existence of subgraphs homeomorphic to $K_5$ or $K_{3,3}$
  • $K_5$ is the complete graph on 5 vertices
  • $K_{3,3}$ is the complete bipartite graph with 3 vertices in each set
• Planar graphs have at most $3V-6$ edges (for $V \geq 3$)
• Every planar graph has a vertex of degree 5 or less
• Planar graphs can be colored using at most 4 colors (Four Color Theorem)

Graph Drawing Algorithms

• Force-directed algorithms (spring embedders) simulate physical forces to position vertices
  • Attractive forces pull connected vertices together
  • Repulsive forces push all vertices apart
  • Iteratively update vertex positions until reaching an equilibrium
• Hierarchical layouts (Sugiyama framework) arrange vertices in layers
  • Minimize edge crossings between layers
  • Optimize vertex ordering within each layer
  • Apply spacing and alignment for readability
• Orthogonal layouts use horizontal and vertical line segments for edges
  • Minimize bends and edge crossings
  • Compact layout with efficient space utilization
• Circular layouts place vertices evenly spaced on a circle
  • Suitable for visualizing cyclic structures or dependencies
• Planar straight-line drawing algorithms (Tutte, Schnyder) embed planar graphs with straight-line edges
  • Guarantee no edge crossings
  • Preserve planarity and graph structure

Planarity Testing Methods

• Kuratowski's algorithm searches for subgraphs homeomorphic to $K_5$ or $K_{3,3}$
  • Systematically checks all possible subgraph configurations
  • Time complexity: $O(V^2)$
• Path addition method incrementally adds edges while maintaining planarity
  • Checks if adding an edge introduces a crossing
  • Efficient for sparse graphs
• Vertex addition method incrementally adds vertices and their incident edges
  • Maintains a planar embedding of the graph
  • Runs in linear time: $O(V)$
• Planarity testing using PQ-trees
  • Represents all possible planar embeddings of a graph
  • Efficient data structure for planarity testing and embedding
• Hopcroft-Tarjan algorithm is a linear-time planarity testing method
  • Depth-first search (DFS) based approach
  • Splits the graph into biconnected components
  • Tests planarity of each component separately

Applications in Computer Science and Networks

• Circuit design and layout
  • Integrated circuits (ICs) require planar layouts
  • Minimize wire crossings and optimize component placement
• Network visualization and analysis
  • Visualize complex network structures (social networks, biological networks)
  • Identify clusters, communities, and key nodes
• Geographic information systems (GIS)
  • Represent and analyze spatial data (maps, road networks)
  • Ensure proper layering and avoid overlaps
• Compiler optimization and code analysis
  • Represent program flow and dependencies using graphs
  • Identify loops, dominators, and reachability
• Resource allocation and scheduling
  • Model tasks and resource constraints as graphs
  • Find optimal assignments and avoid conflicts

Challenges and Advanced Topics

• Crossing number problem seeks the minimum number of edge crossings in a graph drawing
  • NP-hard problem, challenging to solve optimally
  • Heuristic and approximation algorithms are used
• Simultaneous embedding aims to draw multiple graphs on the same vertex set
  • Minimize edge crossings between graphs
  • Applications in comparative analysis and graph alignment
• Dynamic graph drawing handles evolving graphs over time
  • Maintain a stable layout while adding or removing vertices and edges
  • Preserve user's mental map of the graph
• 3D graph drawing extends graph visualization to three dimensions
  • Utilize depth and perspective to convey additional information
  • Challenges in occlusion, navigation, and interaction
• Confluent drawing allows edge bundling and merging
  • Reduce visual clutter in dense graphs
  • Represent shared paths and group related edges

Practice Problems and Exercises

• Determine the planarity of given graph examples
  • Apply planarity testing algorithms (Kuratowski's, path addition, vertex addition)
  • Justify the results using planarity properties and theorems
• Draw planar graphs using different layout algorithms
  • Force-directed, hierarchical, orthogonal, circular layouts
  • Compare the resulting drawings in terms of readability and aesthetics
• Verify Euler's formula for connected planar graphs
  • Count the number of vertices, edges, and faces in planar graph examples
  • Check if the formula $V - E + F = 2$ holds
• Find the minimum number of colors required to color a planar graph
  • Apply the Four Color Theorem
  • Use graph coloring algorithms (greedy coloring, backtracking)
• Identify subgraphs homeomorphic to $K_5$ or $K_{3,3}$ in non-planar graphs
  • Understand the concept of graph homeomorphism
  • Recognize the forbidden subgraphs that characterize non-planarity
• Implement graph representation techniques (adjacency matrix, adjacency list)
  • Convert between different representations
  • Analyze the space and time complexity of each representation
• Solve real-world problems using graph drawing and planarity concepts
  • Design circuit layouts, network visualizations, or geographic maps
  • Apply appropriate graph drawing algorithms and planarity testing methods