Fact-checked by Grok 2 weeks ago

Geometric graph theory

Geometric graph theory is a branch of graph theory that examines the combinatorial and geometric properties of graphs drawn in the Euclidean plane, where vertices are represented as points in general position and edges as straight-line segments, potentially allowing crossings.^[1] These graphs, often called geometric graphs, extend classical abstract graph theory by incorporating spatial constraints and embeddings, focusing on phenomena such as edge intersections, planarity, and extremal configurations.^[2] In contrast, topological graphs generalize this by permitting curvilinear edges instead of straight lines, broadening the study to include more flexible embeddings while preserving topological properties.^[2] The field originated in the early 20th century with foundational problems posed by mathematicians like Heinz Hopf and Erika Pannwitz in 1934, who investigated the maximum number of edges in certain geometric graphs without specific substructures.^[2] Paul Erdős significantly advanced the area in 1946 through his work on diameter graphs and distinct distances among points, establishing key bounds such as the fact that the diameter graph of n points in the plane has at most n edges.^[2] By the late 20th century, geometric graph theory had emerged as a distinct discipline, intersecting with combinatorial geometry and computational geometry, driven by extremal problems analogous to Ramsey and Turán theorems but adapted to planar embeddings.^[1] Central topics include the crossing number of a graph—the minimum number of edge crossings in any drawing—and related extremal questions, such as the maximum number of edges in a geometric graph avoiding certain forbidden subgraphs like K_{3,3}^ or multiple disjoint edges.^[1] Notable results encompass Fáry's Theorem, which guarantees that every planar graph admits a crossing-free straight-line embedding, and the Crossing Lemma, stating that for a simple graph with n vertices and e edges, the crossing number satisfies cr(G) ≥ c e³ / n² for some constant c.^[1] The Hanani-Tutte Theorem further connects even-crossing drawings to planarity, providing a criterion for redrawability without crossings.^[1] These theorems underpin applications in areas like network design, VLSI layout, and sensor networks, where geometric constraints model real-world spatial relationships.^[3]

Fundamentals

Definition and Basic Concepts

Geometric graph theory is a branch of mathematics that examines the combinatorial and geometric properties of graphs embedded in the Euclidean plane. A geometric graph is defined as an abstract graph whose vertices are represented by distinct points in the plane and whose edges are straight-line segments connecting these points, allowing for possible intersections between edges. More generally, edges can be Jordan arcs—simple continuous curves from one vertex to another without self-intersections—leading to the related notion of topological graphs when curves are not restricted to straight lines. This embedding introduces spatial constraints and geometric incidences, such as crossings, that are absent in purely abstract graph representations.^[2]^[1]^[4] To understand geometric graphs, it is essential to distinguish them from abstract graphs, which consist solely of a set of vertices and edges defined by adjacency relations without any spatial layout. In an abstract graph, edges represent connections without regard to position or intersection; a geometric realization, however, maps vertices to points in \mathbb{R}^2 and edges to curves, thereby incorporating metric and topological properties like distances, angles, and crossing points. This realization does not presuppose planarity, meaning edges may cross at interior points, creating a drawing that captures both graph-theoretic and Euclidean geometric features. Basic properties include the requirement that vertices are in general position (no three collinear, unless specified otherwise) and that edges are non-self-intersecting, though distinct edges may share interior points at crossings. A simple geometric graph further prohibits multiple edges between the same pair of vertices and self-loops, ensuring a clean embedding without degenerate overlaps.^[5]^[2]^[1] Illustrative examples highlight these concepts. A triangle forms a simple geometric graph where three points in the plane are connected by straight-line edges with no crossings, embodying a cycle in the abstract sense but with precise Euclidean lengths and angles. In contrast, the complete graph K_4 on four points in convex position, with all six possible edges drawn as straight lines, necessarily includes crossings, as the diagonals intersect at an interior point, demonstrating how geometric embeddings can force intersections even in non-planar abstract graphs. These basic constructions underscore the interplay between combinatorial structure and geometric placement central to the field.^[1]^[4]

Historical Development

Geometric graph theory emerged in the early 20th century as a subfield of graph theory intertwined with combinatorial topology and the study of planar graphs. A foundational contribution came from Kazimierz Kuratowski, who in 1930 characterized planar graphs by identifying forbidden subgraphs (subdivisions of K_5 or K_{3,3}) that prevent embedding in the plane without crossings, thereby establishing criteria for geometric realizations of graphs.^[6] This theorem, bridging abstract graph properties with topological embeddings, influenced subsequent investigations into how graphs could be drawn with specific geometric constraints.^[7] In the 1930s and 1940s, early extremal problems specific to geometric settings gained prominence. Heinz Hopf and Erika Pannwitz demonstrated in 1934 that any geometric graph on n points with no two disjoint edges contains at most n edges, initiating studies on edge restrictions under geometric conditions.^[2] The field progressed with embedding theorems in the late 1940s: István Fáry proved in 1948 that every simple planar graph admits a crossing-free straight-line drawing in the plane.^[1] Key figures during this era included Hugo Hadwiger, whose 1943 conjecture on graph contractions linked chromatic numbers to clique minors and impacted geometric coloring problems, and Gerhard Ringel, who advanced embeddings through his 1952 proof of the Heawood conjecture for nonorientable surfaces.^[7] These developments, influenced by combinatorial geometry and topology, solidified the theoretical underpinnings of geometric graph theory in the 1930s–1950s.^[2] Post-1960s, the discipline expanded with computational aspects, including algorithms for realizing straight-line embeddings, and the study of intersection graphs such as unit disk graphs.^[1] By the 1980s and 2000s, focus shifted from pure planarity to broader constraints like unit distances—sparked by Paul Erdős's 1946 query on the minimum number of distinct distances among n points in the plane—and crossing properties in non-planar settings.^[2] Recent evolution has emphasized Ramsey-type results for geometric graphs, with seminal contributions from János Pach and collaborators since the 1990s exploring monochromatic substructures under geometric embeddings.^[4]

Types of Geometric Graphs

Planar Straight-Line Graphs

Planar straight-line graphs are a fundamental subclass of geometric graphs, consisting of a finite set of distinct points in the Euclidean plane as vertices and straight-line segments connecting pairs of these points as edges, with the condition that no two edges intersect except at shared endpoints. The vertices are typically placed in general position, ensuring no three points are collinear, which prevents unintended degeneracies in the embedding. This structure inherently satisfies planarity, as the straight-line edges divide the plane into non-overlapping regions without crossings.^[1] Key properties of planar straight-line graphs include their adherence to classical planarity constraints, such as the bound on the number of edges. A maximal planar straight-line graph on v \geq 3 vertices is a triangulation, meaning every face—including the unbounded outer face—is a triangle bounded by three edges. For such connected graphs, Euler's formula applies: v - e + f = 2, where e denotes the number of edges and f the number of faces. Given that each triangular face is incident to three edges and each edge is shared by two faces, the relation $2e = 3f follows, leading to e = 3v - 6 and f = 2v - 4. These relations establish the structural density of maximal instances, ensuring no additional straight-line edge can be added without introducing a crossing.^[8]/03:_Graph_Theory/15:_Planar_Graphs/15.02:_Eulers_Formula)^[9] Representative examples of planar straight-line graphs include triangulations of finite point sets in the plane. The convex hull of the point set forms the boundary of the outer face in any such triangulation, providing a simple non-maximal case. A prominent maximal example is the Delaunay triangulation, which connects points such that no point lies inside the circumcircle of any triangle; this construction not only maximizes the minimum angle among all possible triangulations but also ensures the empty circumcircle property for each face.^[10] The construction of planar straight-line graphs often involves embedding abstract planar graphs with straight edges. Fáry's theorem guarantees that every simple planar graph admits such an embedding without crossings, a result independently proved by Wagner in the same year. This theorem enables the realization of any planar graph as a planar straight-line graph, with algorithms like the shift method producing O(n)-time drawings on a grid of size O(n) × O(n) for n-vertex maximal plane graphs.^[8]^[11]

Intersection Graphs

In geometric graph theory, an intersection graph is formed from a collection of geometric objects in the plane or higher dimensions, where each vertex corresponds to one object, and an edge exists between two vertices if and only if their associated objects intersect.^[12] This framework generalizes various graph classes by varying the types of objects, such as disks, line segments, or curves, allowing the study of combinatorial properties through geometric realizations.^[12] Prominent subclasses include unit disk graphs, where vertices represent disks of equal radius (typically unit radius) and edges connect intersecting disks.^[13] These graphs model wireless networks where nodes communicate if within a fixed range, capturing proximity-based connectivity.^[13] Interval graphs form another key example, arising from intervals on a real line, with edges between overlapping intervals; they represent scheduling problems where tasks conflict if their time periods overlap.^[14] Further examples encompass circle graphs, defined as intersection graphs of chords in a circle, where vertices correspond to chords and edges indicate crossings inside the circle.^[15] String graphs generalize this to intersections of arbitrary continuous curves (strings) in the plane, without self-intersections, modeling more flexible topological interactions.^[16] Certain intersection graphs exhibit strong structural properties. Chordal graphs, characterized by the absence of induced cycles longer than three vertices, are precisely the intersection graphs of subtrees in a tree.^[17] Moreover, classes like interval graphs and chordal graphs are perfect, meaning the chromatic number equals the clique number for every induced subgraph, enabling efficient coloring and optimization.^[18] Recognition of intersection graphs varies in complexity. Interval graphs can be recognized in linear time using lexicographic breadth-first search to verify a consecutive ones property in their maximal cliques matrix.^[19] In contrast, recognizing general string graphs is NP-complete, as it requires determining if a graph admits a curve intersection representation, a problem both NP-hard and in NP.^[16]^[20]

Other Specialized Graphs

Polyhedral graphs are the 1-skeletons of three-dimensional convex polyhedra, which can be realized as straight-line embeddings in the plane due to their inherent planarity. These graphs are characterized as simple, 3-connected planar graphs, where every face is bounded by a cycle and the embedding corresponds to a projection of the polyhedral structure without crossings.^[21] Visibility graphs generalize point sets by incorporating obstacles, such as simple polygons or line segments, in the plane. In this framework, vertices represent points (often the vertices of the obstacles), and edges connect pairs of points if the straight-line segment between them lies entirely within the free space, unobstructed by any obstacle interiors or boundaries except at endpoints.^[22] Flip graphs arise in the context of triangulations of point sets or polygons, where vertices correspond to distinct triangulations, and edges represent elementary transformations known as flips. A flip replaces one diagonal of a convex quadrilateral in the triangulation with the opposite diagonal, connecting two triangulations that differ by exactly this operation. These graphs are connected, meaning any two triangulations can be transformed into each other via a sequence of flips, and for a set of n points in general position, the diameter—the maximum flip distance between any pair—is Θ(n²).^[23]

Key Theorems and Results

Embeddings and Planarity

In geometric graph theory, embeddings of graphs in the Euclidean plane play a central role in determining whether abstract planar graphs can be realized with specific geometric constraints, such as straight-line edges or particular intersection patterns, while preserving non-crossing properties. A key focus is on straight-line embeddings, where vertices are mapped to points in the plane and edges to line segments, ensuring no unintended crossings occur. These realizations bridge combinatorial structure with geometric configuration, enabling applications in visualization and computational geometry. Seminal results characterize the existence of such embeddings for planar graphs, often relying on connectivity conditions or auxiliary geometric constructions. Fáry's theorem asserts that every simple planar graph admits a straight-line embedding in the plane without edge crossings.^[24] Published in 1948, this result independently rediscovered an earlier idea by Wagner from 1936, confirming that curved-edge planar drawings can always be "straightened" while maintaining planarity. The proof involves iteratively adjusting vertex positions to convexify faces, starting from a combinatorial embedding and using properties of planar maps to avoid crossings. A practical algorithmic realization of Fáry's theorem employs canonical orderings, introduced by de Fraysseix, Pach, and Pollack in 1990, where vertices are added sequentially in a linear-time process that maintains convexity of the outer face and non-crossing edges through barycentric coordinate assignments. Steinitz's theorem provides a characterization in three dimensions, stating that a graph is the 1-skeleton of a convex polyhedron if and only if it is planar and 3-connected. Formulated in 1928, this theorem links graph connectivity to polyhedral realizability, implying that such graphs have straight-line embeddings in the plane as a projection of their 3D convex hull. The sufficiency direction constructs coordinates for vertices using facial cycles and linear programming to ensure convexity, while the necessity follows from Euler's formula and separation properties of convex polyhedra. This result extends planar embeddings by embedding the graph on the boundary of a 3D object, with the 3-connectedness ensuring a unique combinatorial embedding up to relabeling. The circle packing theorem establishes that every simple planar graph is the contact graph of a collection of non-overlapping circles in the plane, where two circles touch externally if and only if the corresponding vertices are adjacent.^[25] First proved by Koebe in 1936 using conformal mapping techniques for multiply connected domains, the theorem was generalized by Thurston in the 1980s through a discrete analogue of the Riemann mapping theorem, applying circle packings to approximate uniformization. Andreev's 1965 work filled gaps for triangulations, completing the picture. High-level proofs involve solving a system of equations for circle radii and centers based on the graph's dual, ensuring tangency via optimization or fixed-point theorems, with the packing being unique up to Möbius transformations fixing the plane. Scheinerman's conjecture, proposed in 1984, posits that every planar graph is the intersection graph of line segments in the plane. Proved affirmatively by Chalopin and Gonçalves in 2009, the result shows that segments can be arranged to intersect precisely when vertices are adjacent, without requiring straight-line non-crossing. The proof decomposes the graph into bipartite subgraphs, each realizable as segment intersections via track layouts and universal point sets, then combines them using layered constructions to preserve intersections. This extends Fáry's framework by allowing crossings in the realization but enforcing intersection patterns, highlighting the flexibility of segment representations for planar graphs.

Intersection and Crossing Properties

In geometric graph theory, the crossing number of a graph G, denoted \mathrm{cr}(G), is defined as the minimum number of edge crossings over all possible drawings of G in the plane, where edges are represented as Jordan arcs and crossings occur only at interior points of edges.^[26] This measure quantifies the inherent non-planarity of graphs and plays a central role in analyzing how edges must intersect when embedded geometrically. For the complete graph K_n, an upper bound on the crossing number is given by

\mathrm{cr}(K_n) \leq \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor,

achieved through specific cylindrical or two-sided drawings that minimize intersections. Exact values are known for small n, such as \mathrm{cr}(K_5) = 1, \mathrm{cr}(K_6) = 3, \mathrm{cr}(K_7) = 9, and \mathrm{cr}(K_8) = 18, often verified through exhaustive enumeration of optimal drawings.^[26] Thrackles represent a class of geometric graphs with highly constrained intersection properties. A thrackle is a drawing of a simple graph in the plane where each edge is a Jordan arc, and every pair of distinct edges intersects exactly once—either at a shared endpoint (if adjacent) or at a proper crossing (if non-adjacent)—with no three edges concurrent at a crossing point.^[27] Introduced informally by John Conway, thrackles explore extremal configurations where intersections are both mandatory and uniquely controlled. Conway's thrackle conjecture posits that no thrackle can have more edges than vertices, i.e., |E| \leq |V|, which would imply thrackles are sparse compared to general graphs.^[27] While the conjecture remains open, it has been established that every thrackle satisfies |E| \leq 2|V| - 3 for |V| \geq 3, providing a linear upper bound on density.^[27] The happy ending problem investigates intersection-free subsets in point sets, linking to convex position and monotone chains. Originating from a question posed by Erdős to Szekeres, it asks for the smallest number ES(k) such that any set of ES(k) points in the plane, in general position (no three collinear), contains a subset of k points forming the vertices of a convex k-gon.^[28] The Erdős–Szekeres theorem resolves this by proving that any such set of at least \binom{2k-4}{k-2} + 1 points contains a convex k-gon, establishing an upper bound on ES(k).^[28] Known exact values include ES(3) = 3, ES(4) = 5, ES(5) = 9, and ES(6) = 17; exact values for larger k remain unknown, with the theorem implying that sufficiently large point sets inevitably form large convex polygons without internal intersections.^[28] The Szemerédi–Trotter theorem provides a foundational bound on incidences that directly informs crossing properties in geometric graphs. It states that for a set of p points and \ell lines in the Euclidean plane, the number of point-line incidences I satisfies

I = O\left( p^{2/3} \ell^{2/3} + p + \ell \right).

^[29] This result is tight up to constants, as shown by lattice point configurations, and applies to crossing counts by modeling edges as lines and potential crossings as incidences between pairs of edges.^[29] In geometric graphs, it implies that drawings with many edges must incur numerous crossings unless structured to avoid high-incidence configurations, influencing bounds on crossing numbers via probabilistic or extremal arguments.^[29] Unit distance graphs exemplify intersection behaviors in geometric settings, where vertices are points in the plane and edges connect pairs at exactly unit distance, drawn as straight-line segments. These graphs inherently permit crossings, as non-adjacent unit segments may intersect. For instance, the Moser spindle, a unit distance graph with 7 vertices and 11 edges, requires crossings in any embedding and serves as a rigid structure demonstrating unavoidable intersections.^[30] More generally, the crossing behaviors of unit distance graphs are studied through k-planar variants, where each edge is involved in at most k crossings; the maximum number of edges in such a graph on n vertices is \Theta(n) for fixed k, contrasting with the denser O(n^{4/3}) edges possible in general unit distance graphs without crossing restrictions.^[31] These properties highlight how unit distances constrain yet amplify intersection complexity in geometric realizations.^[31]

Chromatic and Ramsey-Type Results

The Hadwiger–Nelson problem seeks to determine the chromatic number of the plane, which is the smallest number of colors required to color all points in the Euclidean plane such that no two points exactly distance 1 apart share the same color. This problem, first posed by Edward Nelson in 1950, building on related work by Hugo Hadwiger from 1945, models the unit distance graph of the plane where vertices are all points in \mathbb{R}^2 and edges connect pairs at unit distance. The chromatic number \chi satisfies $5 \leq \chi \leq 7.^[32] The upper bound of 7 arises from a 7-coloring based on a hexagonal tiling of the plane, where each tile is a regular hexagon with diameter slightly less than 1, ensuring no monochromatic unit distances within or across tiles; this construction dates to work by John Isbell in 1950. The lower bound of 4 was established in 1961 by the Moser spindle, a finite unit distance graph with 7 vertices that requires 4 colors and embeds in the plane without crossings. This graph consists of two rhombi with 60-degree angles, connected in a way that forces a 4-coloring. In 2018, Aubrey de Grey improved the lower bound to 5 by constructing a unit distance graph with 1581 vertices that is not 4-colorable, using a computer-assisted search starting from the Moser spindle and Golomb graph. The Golomb graph, a 10-vertex unit distance graph also requiring 4 colors, played a role in exploring such constructions but does not achieve the bound of 5. These finite unit distance graphs provide lower bounds for the chromatic number of the plane, as the plane's coloring must accommodate any finite subgraph.^[33]^[32] Ramsey-type results in geometric graph theory examine guaranteed monochromatic structures in edge-colored geometric graphs, often with vertices in convex position to leverage geometric constraints like non-crossing edges. Unlike classical Ramsey theory, geometric variants exploit planarity and intersection properties to yield tighter bounds. For example, in a 2-edge-coloring of the complete geometric graph on n points in convex position, off-diagonal Ramsey numbers quantify the minimal n ensuring a monochromatic triangle in one color or a monochromatic \ell-cycle in the other. Specifically, for \ell \geq 3, the geometric Ramsey number R_g(C_3, C_\ell) = 3\ell - 3, meaning any 2-coloring of the edges of the complete geometric graph on $3\ell - 2 vertices contains either a monochromatic 3-cycle (triangle) or a monochromatic \ell-cycle, while there exists a coloring of $3\ell - 4 vertices avoiding both. Similar results hold for triangulated cycles, with R_g(D_3, D_\ell) = 3\ell - 3. These bounds highlight how geometric embeddings restrict Ramsey numbers compared to abstract graphs, where classical off-diagonal numbers grow exponentially. Broader results include guarantees for monochromatic non-crossing paths or stars versus outerplanar graphs, such as R_g(P_k, H) \leq (k-1)(\ell-1) + 1 for an outerplanar graph H with \ell vertices.^[34]

Applications

In Computational Geometry

In computational geometry, geometric graph theory underpins efficient algorithms for embedding graphs while respecting geometric constraints such as straight-line edges and non-crossing conditions. A fundamental task is computing straight-line embeddings of planar graphs, which map vertices to points in the plane such that edges are straight segments without intersections. The seminal algorithm by de Fraysseix, Pach, and Pollack achieves this in linear time O(n), producing a crossing-free drawing on a grid of size O(n) × O(n), establishing that every planar graph admits such an embedding with quadratic area.^[35] Recognizing whether a given straight-line drawing of a graph is planar—i.e., free of edge crossings—relies on geometric tests for line segment intersections. The Bentley-Ottmann sweep line algorithm efficiently detects all intersections in O((n + k) log n) time, where n is the number of segments and k is the number of reported intersections, enabling verification of planarity in geometric realizations. Data structures derived from geometric graphs play a crucial role in solving proximity problems. Delaunay triangulations, which maximize the minimum angle among all triangulations of a point set, serve as duals to Voronoi diagrams and facilitate nearest neighbor queries in O(log n) time after preprocessing. Their construction can be performed in O(n log n) time using Fortune's sweep line algorithm, which simulates a parabolic wavefront to build the Voronoi diagram and extract the triangulation. These structures are essential for applications like mesh generation and spatial indexing, where the triangulation encodes connectivity based on empty circle properties. Key optimization problems in geometric graph drawings include minimizing edge crossings, which is NP-hard even for straight-line representations. Approximation algorithms provide guarantees, such as the O(\log^3 n)-approximation for the sum of vertices and crossings in straight-line drawings of bounded-degree graphs.^[36] More recent advances, as of 2022, achieve subpolynomial approximations O(2^{O((\log n)^{7/8} \log \log n)} \cdot \Delta) for the crossing number in general graphs.^[37] Visibility graphs, modeling line-of-sight connections in polygons, apply the art gallery theorem to guarding problems; for instance, they help select vertex guards to cover a simple polygon with at most floor(n/3) points, as proven by Chvátal, with algorithms computing such guards in polynomial time for special cases like orthogonal polygons. Delaunay triangulations, referenced as a canonical planar straight-line graph, further support these visibility computations by providing a triangulation backbone for polygon decomposition. Certain recognition problems in geometric graph theory exhibit high complexity. Recognizing unit disk graphs—intersection graphs of equal-radius disks in the plane—is NP-hard, as shown by reduction from 3-SAT, implying challenges in verifying geometric realizations for wireless network modeling.

In Network Theory

Geometric graph theory finds significant applications in network theory, particularly in modeling real-world communication systems where spatial constraints influence connectivity and performance. Geometric graphs, such as unit disk graphs and visibility graphs, provide a natural framework for representing networks embedded in Euclidean space, enabling the analysis of connectivity, routing efficiency, and interference under physical limitations like transmission ranges or line-of-sight requirements. These models are essential for designing robust infrastructures in environments where nodes have fixed or dynamic positions, such as sensor deployments or mobile ad hoc setups.^[38]^[39] In wireless sensor networks (WSNs), unit disk graphs model connectivity by assuming each node has a fixed transmission range, represented as equal-radius disks centered at node positions; two nodes are connected if their disks intersect. This abstraction captures the geometric constraints of signal propagation, facilitating the study of network topology formation and maintenance. For instance, unit disk graphs are used to ensure reliable communication in dense deployments, where edge existence depends solely on Euclidean distance. Coverage problems in WSNs, which aim to monitor an area or targets with minimal sensor overlap or redundancy, often leverage intersection graphs derived from these models; the sensing regions form an intersection graph where overlapping areas indicate potential coverage redundancy. Seminal work has shown that optimal coverage in such graphs is NP-hard, but geometric properties allow for efficient approximations using techniques like Voronoi diagrams to partition the space and select representative sensors.^[38]^[40]^[41] Spatial networks, which embed nodes in physical space for applications like urban infrastructure or environmental monitoring, utilize Euclidean minimum spanning trees (EMSTs) for energy-efficient routing. An EMST connects all nodes with minimal total edge length based on Euclidean distances, serving as a low-cost backbone for data dissemination; in wireless settings, it approximates minimum-energy broadcast routing by bounding the power required for transmissions along tree edges. This approach is particularly valuable in static ad hoc networks, where EMST-based heuristics achieve approximation ratios between 6 and 12 for NP-hard energy minimization problems. Visibility graphs further enhance modeling for line-of-sight (LoS) communications, where edges exist only between nodes with unobstructed paths, avoiding barriers like buildings; these graphs are critical for urban wireless networks, enabling path planning that respects terrain visibility. In obstructed environments, LoS networks extend random geometric graphs by incorporating visibility polygons, improving predictions of connectivity in realistic scenarios.^[42]^[43]^[44] Practical examples illustrate these applications' impact. In ad hoc networks, geometric embeddings—assigning nodes to spatial positions—minimize interference by optimizing transmission radii and channel assignments based on disk overlaps, reducing concurrent transmissions in overlapping regions to enhance throughput. For instance, algorithms that bound the interference degree in unit disk realizations achieve constant-factor approximations for scheduling, crucial in dynamic scenarios like vehicular networks. Social networks with spatial embeddings model user interactions influenced by physical proximity, using geometric graphs where edges form probabilistically based on distance in a metric space; this captures clustering in location-based services, such as friend recommendations in geo-social platforms.^[45]^[46]^[39] Key challenges in applying geometric graphs to network theory include scalability for large-scale deployments and developing approximations for NP-hard problems like routing. In expansive WSNs with thousands of nodes, computing exact structures like EMSTs or connected dominating sets (CDS) becomes computationally intensive due to the quadratic complexity of distance calculations, necessitating distributed algorithms that trade accuracy for efficiency. For routing, constructing a minimum CDS in unit disk graphs—which forms a connected backbone for message forwarding—is NP-hard, but constant-factor approximations (e.g., 8-approximation) enable practical virtual backbones that reduce routing overhead while maintaining connectivity. Recent advances in scalable processing, such as sampling-based methods for random geometric graphs, address these issues by ensuring transferability across network sizes without full recomputation.^[47]^[48]^[49]

References

[1]
[PDF] 10 GEOMETRIC GRAPH THEORY - CSUN
Geometric graph theory focuses on combinatorial and geometric properties of graphs drawn in the plane by straight-line edges (or, more generally, by edges ...
[2]
[PDF] The Beginnings of Geometric Graph Theory
Geometric graphs (topological graphs) are graphs drawn in the plane with possi- bly crossing straight-line edges (resp., curvilinear edges). Starting with a ...
[3]
[PDF] Geometric Graph Theory and Wireless Sensor Networks
The arrangement A of a set S of line segments in the plane is the incidence structure among the vertices, edges, and cells of the arrangement, defined in the ...<|control11|><|separator|>
[4]
Geometric Graph Theory - Surveys in Combinatorics, 1999
May 5, 2013 · Summary A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are ...
[5]
Combinatorial Geometry | Wiley Online Books
A complete, self-contained introduction to a powerful and resurging mathematical discipline. Combinatorial Geometry presents and explains with complete proofs
[6]
Sur le problème des courbes gauches en Topologie - EuDML
Kuratowski, Casimir. "Sur le problème des courbes gauches en Topologie." Fundamenta Mathematicae 15.1 (1930): 271-283. <http://eudml.org/doc/ ...
[7]
Milestones in Graph Theory - American Mathematical Society
In this timeline we list some of the important publications and events in the history of graph theory, from the 18th century to the present day. 1735 Euler ...
[8]
[PDF] Planar Straight-Line Drawing Algorithms - Brown CS
Planar straight-line drawings map edges to straight-line segments. Algorithms use shift and realizer methods to construct grid drawings. Every planar graph ...
[9]
[PDF] 3 Planar graphs - CS@Purdue
We begin by recollecting common definitions needed in this section. A graph is an ordered pair of sets,. G = (V,E). The elements in V are called vertices and ...
[10]
[PDF] Delaunay Triangulation (chapter 9) - CS@Purdue
A triangulation of a point set is a subdivision whose vertices are the points and that has a maximal number of edges. ▷ The bounded faces are triangles ...
[11]
Fáry Theorem -- from Wolfram MathWorld
Fáry's theorem states that any simple planar graph can be drawn in a planar straight line embedding, i.e., using straight line segments for edges, ...
[12]
[PDF] All-Pairs Shortest Paths in Geometric Intersection Graphs
More generally, given a set S of n geometric objects, its intersection graph G(S) is defined by creating one vertex for every object of S and an (undirected, ...
[13]
[PDF] Shortest Path Separators in Unit Disk Graphs - arXiv
Jul 22, 2024 · One common type of geometric intersection graph is the unit disk graph, which are geometric intersection graphs of disks with diameter 1. These ...
[14]
Interval Graph - an overview | ScienceDirect Topics
An interval graph is defined as a graph where each vertex can be associated with an interval on the real line, such that two vertices are adjacent if and ...
[15]
Circle Graph - an overview | ScienceDirect Topics
A graph is called a circle graph if each of its vertices can be associated with a chord on a circle in such a way that two vertices are adjacent if and only if ...
[16]
String graphs. II. recognizing string graphs is NP-hard - ScienceDirect
J Kratochvíl. String graphs. “Graphs and Other Combinatorial Topics,” Proceedings, 3rd Czechoslovak Symposium on Graph Theory, Teubner-Texte Math., 59 (1983) ...
[17]
[PDF] Intersection Graphs of Subtrees in Trees Are Exactly the Chordal ...
The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than.
[18]
Classes of perfect graphs - ScienceDirect.com
Oct 6, 2006 · In this paper we survey 120 of these classes, list their fundamental algorithmic properties and present all known relations between them.
[19]
[PDF] Linear Algorithms to Recognize Interval Graphs and - IC-Unicamp
Theorem 2.1. Algorithm 1 correctly recognizes interval graphs, and can be implemented to run in 0(n+e) time. Proof sketch.
[20]
[PDF] Recognizing String Graphs in NP
The result has consequences for the computational complexity of problems in graph drawing, and topological inference.
[21]
[PDF] arXiv:2212.14323v1 [math.CO] 29 Dec 2022
Dec 29, 2022 · A polyhedral graph is a 3-connected planar graph. We find the least possible order p(k, a) of a polyhedral graph containing a k-independent ...Missing: geometric | Show results with:geometric
[22]
[PDF] 33 VISIBILITY - CSUN
INTRODUCTION. In a geometric context, two objects are “visible” to each other if there is a line segment connecting them that does not cross any obstacles.<|separator|>
[23]
[PDF] Flip Graphs of Bounded Degree Triangulations - TU Graz
The diameter of the flip graph, which is an upper bound on the flip distance, is known to be Θ(n) if S is in convex position [14], and Θ(n2) if S is in general ...
[24]
[PDF] arXiv:0909.0816v3 [math.GT] 20 Nov 2009
Nov 20, 2009 · The 1-skeleton of Pl is the Cayley graph of the standard presentation of the symmetric group on l letters: Sl = hσ1,··· ,σl−1 |σ2 i = 1 ...
[25]
[PDF] A poset-based approach to embedding median graphs in ...
Graphs which can be isometrically embedded in a hypercube are called partial cubes. While not obvious from the definition, median graphs are in fact partial.
[26]
[PDF] On straight line representation of planar graphs.
In the present note I shall prove that if a finite graph can be represented on the plane at all, it can be represented with straight segments as edges too, ...
[27]
Kontaktprobleme der konformen Abbildung - Virtuelles Archiv der SAW
Koebe, Paul: Kontaktprobleme der konformen Abbildung.. In: Sächsische Akademie der Wissenschaften zu Leipzig (Hrsg.): Berichte über die Verhandlungen der ...Missing: 1936 PDF
[28]
[PDF] The Graph Crossing Number and its Variants: A Survey
Dec 20, 2011 · Abstract. The crossing number is a popular tool in graph drawing and visualization, but there is not really just one crossing number; ...
[29]
[PDF] On Conway's Thrackle Conjecture - NYU Courant
We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.
[30]
[PDF] A combinatorial problem in geometry - Numdam
SZEKERES. A combinatorial problem in geometry. Compositio Mathematica, tome 2 ... FIRST PROOF. The basis of the first proof is a combinatorial theorem of.
[31]
Extremal problems in discrete geometry | Combinatorica
Mar 14, 1983 · In this paper, we establish several theorems involving configurations of points and lines in the Euclidean plane.
[32]
[PDF] Structure of Extremal Unit Distance Graphs - Scholar Commons
(Crossing Number, [6]) The crossing number cr(G) of a graph. G is the minimum number of edge crossings in any drawing of G in the plane. Theorem 4. (Crossing ...
[33]
[PDF] 1-planar unit distance graphs - arXiv
Jun 4, 2025 · For any k ≥ 0, a graph G is called k-planar if G can be drawn in the plane such that each edge is involved in at most k crossings. Let ek(n) ...
[34]
[1804.02385] The chromatic number of the plane is at least 5 - arXiv
Apr 8, 2018 · We present a family of finite unit-distance graphs in the plane that are not 4-colourable, thereby improving the lower bound of the Hadwiger- ...
[35]
Moser Spindle -- from Wolfram MathWorld
The Moser spindle is the 7-node unit-distance graph illustrated above (Read and Wilson 1998, p. 187). It is sometimes called the Hajós graph.
[36]
[PDF] on geometric graph ramsey numbers
We also give a series of more general estimates on off-diagonal geometric graph Ramsey numbers in the same spirit. Finally we investigate the existence of.
[37]
How to draw a planar graph on a grid | Combinatorica
Jan 12, 1989 · De Fraysseix, H., Pach, J. & Pollack, R. How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990). https://doi.org/10.1007 ...
[38]
Improved Approximations of Crossings in Graph Drawings and VLSI ...
We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing on the plane of a bounded degree ...
[39]
https://www.usenix.org/legacy/event/wosn/tech/full_papers/Bonato.pdf
[40]
[PDF] A Geometric Model for On-line Social Networks∗ - USENIX
In geometric graph models, nodes are identified with points in a metric space, and edges are introduced by probabilistic rules that depend on the proximity of ...
[41]
[PDF] Coverage in Wireless Ad-hoc Sensor Networks
Abstract—Sensor networks pose a number of challenging conceptual and optimization problems such as location, deployment, and tracking [1].
[42]
[PDF] On Solving Coverage Problems in a Wireless Sensor Network Using ...
On Solving Coverage Problems in a Wireless. Sensor Network Using Voronoi Diagrams. Anthony Man–Cho So1 and Yinyu Ye2. 1 Department of Computer Science ...
[43]
[PDF] Minimum-Energy Broadcast Routing in Static Ad Hoc Wireless ...
A cornerstone to the analysis of the up- per bounds is an elegant structure property of Euclidean MST, which is explored in Section VI. Finally in Section ...
[44]
Minimum-energy broadcast routing in static ad hoc wireless networks
By exploring geometric structures of Euclidean MSTs, we have been able to prove that the approximation ratio of MST is between 6 and 12, and the approximation ...
[45]
[PDF] Line-of-Sight Networks - Cornell: Computer Science
Abstract. Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region ...
[46]
Minimizing interference in ad hoc and sensor networks
Reducing interference is one of the main challenges in wireless communication, and particularly in ad hoc networks. The amount of interference experienced ...
[47]
Minimizing interference in ad-hoc networks with bounded ... - arXiv
Feb 14, 2011 · We consider a topology control problem in which we are given a set of n sensors in the plane and we would like to assign a communication radius ...Missing: embeddings | Show results with:embeddings
[48]
Simulations of large-scale WiFi-based wireless networks
In this paper we review computational and algorithmic challenges of high-fidelity simulations of such WiFi-based wireless communication and computing networks, ...
[49]
[PDF] A Better Theoretical Bound to Approximate Connected Dominating ...
Connected Dominating Set is widely used as virtual backbone in wire- less Ad-hoc and sensor networks to improve the performance of transmission and routing ...
[50]
[PDF] Graph Neural Networks in Large Scale Wireless Communication ...
Oct 1, 2025 · In this work, we provide a formal theoretical foundation for transferability on Random Geometric Graphs (RGGs), a sparse and widely used model ...<|control11|><|separator|>