5.1 Bentley-Ottmann algorithm

Geometric graphs blend graph theory and computational geometry, representing spatial relationships as vertices and edges in Euclidean space. They're crucial for modeling real-world structures like road networks and circuit layouts, capturing spatial connectivity efficiently.

The Bentley-Ottmann algorithm is a key tool for detecting intersections in geometric graphs. It uses a plane sweep approach to find all intersections between line segments, running in O((n + k) log n) time, where n is the number of segments and k is the number of intersections.

Fundamentals of geometric graphs

• Geometric graphs combine principles from graph theory and computational geometry
• Represent spatial relationships between objects as vertices and edges in Euclidean space
• Edges typically correspond to straight line segments between vertices

Euclidean graphs

Top images from around the web for Euclidean graphs

• 

  computational geometry - Divide-and-conquer approach for finding the closest pair of points ... View original

  Is this image relevant?

• 

  Minimum spanning tree - formulasearchengine View original

  Is this image relevant?

• 

  Eulerian path - Wikipedia View original

  Is this image relevant?

• 

  computational geometry - Divide-and-conquer approach for finding the closest pair of points ... View original

  Is this image relevant?

• 

  Minimum spanning tree - formulasearchengine View original

  Is this image relevant?

1 of 3

Top images from around the web for Euclidean graphs

• 

  computational geometry - Divide-and-conquer approach for finding the closest pair of points ... View original

  Is this image relevant?

• 

  Minimum spanning tree - formulasearchengine View original

  Is this image relevant?

• 

  Eulerian path - Wikipedia View original

  Is this image relevant?

• 

  computational geometry - Divide-and-conquer approach for finding the closest pair of points ... View original

  Is this image relevant?

• 

  Minimum spanning tree - formulasearchengine View original

  Is this image relevant?

1 of 3

• Graphs embedded in Euclidean space with vertices as points and edges as straight line segments
• Edge weights often correspond to Euclidean distances between vertices
• Useful for modeling road networks, circuit layouts, and other spatial structures

Proximity graphs

• Graphs where edges are determined by proximity relationships between vertices
• Include structures like Delaunay triangulations and nearest neighbor graphs
• Capture local connectivity information in point sets

Geometric spanners

• Subgraphs that approximate distances in the original graph within a constant factor
• Provide efficient approximations for shortest path problems
• Balance between sparsity and distance preservation

Theta graphs

• Divide space around each vertex into cones and connect to closest vertex in each cone
• Guaranteed spanning ratio depending on number of cones used
• Efficient to construct and query for approximate shortest paths

Yao graphs

• Similar to Theta graphs but connect to k nearest neighbors in each cone
• Provide trade-off between spanner quality and number of edges
• Used in wireless network topology control

Minimum spanning trees

• Connect all vertices with minimum total edge weight
• Fundamental structure in network design and clustering

Euclidean MST

• Minimum spanning tree where edge weights are Euclidean distances
• Can be computed efficiently using Delaunay triangulation
• Applications in facility location and image segmentation

Relative neighborhood graph

• Connect two points if no other point is closer to both
• Superset of Euclidean MST with bounded spanning ratio
• Useful in pattern recognition and wireless networking

Delaunay graphs

• Dual graph of the Voronoi diagram of a point set
• Maximizes the minimum angle of all triangles in the triangulation

Relationship to Voronoi diagrams

• Edges in Delaunay graph correspond to adjacent Voronoi cells
• Vertices of Voronoi diagram are circumcenters of Delaunay triangles
• Provides efficient way to compute nearest neighbors

Properties and applications

• Guaranteed to contain the Euclidean minimum spanning tree
• Used in mesh generation for finite element methods
• Applications in terrain modeling and spatial interpolation

Gabriel graphs

• Connect two points if their diametral circle contains no other points
• Subgraph of Delaunay triangulation with similar properties

Construction algorithms

• Can be constructed in O(n log n) time using Voronoi diagram
• Incremental algorithms available for dynamic point sets
• Efficient parallel construction algorithms exist

Applications in networking

• Used in topology control for wireless networks
• Provide good trade-off between connectivity and power efficiency
• Basis for localized routing algorithms in ad hoc networks

Intersection graphs

• Represent intersections between geometric objects as graph edges
• Capture spatial relationships in various geometric structures

Unit disk graphs

• Connect vertices if their unit disks intersect
• Model wireless network connectivity
• NP-hard problems on general graphs often tractable on unit disk graphs

Visibility graphs

• Connect vertices if they are visible to each other (unobstructed line of sight)
• Used in motion planning and shortest path computations
• Efficient construction using plane sweep algorithms

Geometric thickness

• Minimum number of planar subgraphs needed to cover all edges of a graph
• Measures how close a graph is to being planar

Book thickness

• Minimum number of pages needed to embed a graph without edge crossings
• Related to stack number in graph drawing
• Known bounds for various graph classes (planar, complete, etc.)

Geometric thickness of complete graphs

• Grows as Θ(√n) for complete graphs on n vertices
• Tight bounds known for small values of n
• Open problems remain for exact values in general case

Geometric routing

• Routing algorithms that use only local geometric information
• Crucial for distributed systems and ad hoc networks

Greedy routing

• Forward message to neighbor closest to destination
• Simple to implement but can fail to reach destination
• Guaranteed to work on certain geometric graphs (Delaunay triangulations)

Face routing

• Route along faces of planar graph to guarantee delivery
• Combine with greedy routing for improved average-case performance
• Basis for many practical geometric routing algorithms

Time complexity analysis

Construction algorithms

• Many geometric graph algorithms have O(n log n) time complexity
• Lower bounds often Ω(n log n) due to sorting requirements
• Some structures (Delaunay triangulation) have O(n) expected time algorithms

Query algorithms

• Efficient data structures enable O(log n) time for many queries
• Trade-offs between construction time, space, and query time
• Approximate queries often allow for faster algorithms

Space complexity considerations

• Many geometric graph structures require O(n) space
• Some applications need compact representations for large datasets
• Succinct data structures balance space usage and query efficiency

Planar graphs in geometry

Straight-line embeddings

• Every planar graph can be drawn with straight-line edges without crossings
• Fáry's theorem guarantees existence on integer grid of size O(n) × O(n)
• Efficient algorithms exist for constructing such embeddings

Tutte embedding

• Produces convex drawings of 3-connected planar graphs
• Based on solving system of linear equations
• Guarantees aesthetic properties like face convexity

Geometric graph coloring

Chromatic number of geometric graphs

• Often lower than for general graphs due to geometric constraints
• Unit disk graphs always 6-colorable, often 3 or 4 colors suffice
• Intersection graphs of geometric objects have bounded chromatic number

Conflict-free coloring

• Assign colors so any neighborhood has a unique color
• Applications in frequency assignment for wireless networks
• Logarithmic number of colors often sufficient

Geometric graph drawing

Force-directed methods

• Model graph as physical system with repulsive and attractive forces
• Iteratively adjust vertex positions to minimize energy
• Produce aesthetically pleasing layouts for many graphs

Spectral drawing

• Use eigenvectors of graph Laplacian to determine vertex positions
• Efficient for large graphs with good algebraic connectivity
• Often combined with force-directed methods for refinement