Fact-checked by Grok 2 weeks ago

Intersection graph

In graph theory, an intersection graph is a graph whose vertices correspond to members of a family of sets, with an edge between two vertices if and only if the corresponding sets have non-empty intersection.^[1] It is a fundamental result that every simple undirected graph is an intersection graph of some family of sets.^[2] This representation captures the overlap patterns among the sets, making intersection graphs a fundamental tool for modeling relational structures where intersections denote interactions or overlaps.^[3] The concept encompasses numerous subclasses defined by specific geometric or combinatorial models, such as interval graphs (where sets are intervals on a line), circular-arc graphs (arcs on a circle), chordal graphs (subtrees of a tree), and permutation graphs (line segments between parallel lines).^[1] These classes often exhibit desirable properties, including being perfect graphs, which allows efficient algorithms for coloring, clique finding, and optimization problems.^[3] Recognition algorithms for many intersection graphs, such as interval and chordal graphs, run in linear time, highlighting their computational tractability.^[1] The study of intersection graphs dates back to 1945, when Edward Szpilrajn-Marczewski proved that every graph is an intersection graph.^[2] Early characterizations of specific classes, such as interval graphs by Gilmore and Hoffman in 1964, who linked them to comparability graphs of interval orders, further developed the field.^[4] Subsequent developments in the 1970s and 1980s expanded the theory to broader classes and applications, including scheduling (e.g., register allocation in compilers), bioinformatics (e.g., protein sequencing), VLSI design (e.g., channel routing), and wireless network modeling (e.g., disk graphs for coverage).^[1] Intersection graphs have since become central to algorithmic graph theory, with ongoing research into recognition, embedding, and extremal properties.^[3]

Definition and Fundamentals

Formal Definition

In graph theory, an intersection graph is formally defined as follows: given a universe U (a ground set of elements) and a family of subsets \mathcal{F} = \{ S_v \subseteq U \mid v \in V \}, where V is a finite set, the intersection graph G = (V, E) has vertex set V in one-to-one correspondence with the subsets in \mathcal{F}, and an edge \{u, v\} \in E if and only if S_u \cap S_v \neq \emptyset.^[1]^[5] The universe U serves as the underlying space over which the sets are defined, allowing the intersections to be meaningfully compared; it can be arbitrary (e.g., real numbers, points in the plane) depending on the specific representation, but the structure of G depends only on the pairwise intersection pattern of the sets in \mathcal{F}.^[1]^[5] This construction provides an intersection representation of G, where the family \mathcal{F} encodes the adjacency relations through set overlaps, enabling various geometric or combinatorial models to realize the same graph; for instance, interval graphs arise when U is the real line and each S_v is a closed interval.^[1]^[5] Intersection graphs are typically considered as simple undirected graphs, meaning they contain no loops (since S_v \cap S_v = S_v \neq \emptyset would imply self-loops, which are excluded) and no multiple edges (as intersections are binary relations without multiplicity).^[1]^[5]

Basic Examples

A simple example of an intersection graph is the path graph P_3, which consists of three vertices v_1, v_2, v_3 with edges between v_1 and v_2, and between v_2 and v_3. This can be represented as the intersection graph of intervals on the real line: assign to v_1 the interval [1,3], to v_2 the interval [2,4], and to v_3 the interval [3,5]. Here, the intervals for v_1 and v_2 intersect at [2,3], the intervals for v_2 and v_3 intersect at [3,4], but the intervals for v_1 and v_3 do not intersect, matching the edges of P_3.^[4] Another basic example is the cycle graph C_4, with four vertices v_1, v_2, v_3, v_4 forming a cycle: edges between v_1-v_2, v_2-v_3, v_3-v_4, and v_4-v_1, but no diagonals. This arises as the intersection graph of four disks in the plane, such as unit disks centered at points arranged in a square with side length slightly less than 2 (e.g., centers at (0,0), (1.5,0), (1.5,1.5), (0,1.5)). Adjacent disks overlap, while opposite disks do not, producing the cycle structure; visually, the overlaps form a ring-like pattern without crossing intersections. The complete graph K_n, where every pair of n vertices is connected by an edge, can be constructed as an intersection graph by assigning to each vertex a set that includes a common element shared by all sets, such as sets S_i = \{i, 0\} for i = 1 to n. Every pair of sets intersects at least at the element 0, ensuring all possible edges, while the unique elements distinguish the vertices; this representation highlights how shared elements drive full connectivity.^[3] In contrast, a disjoint union of edges, such as two isolated edges (four vertices with only two non-adjacent edges), serves as an intersection graph using non-intersecting pairs of sets: for one edge, use sets A = \{1,2\} and B = \{1,3\} that intersect at 1; for the other, C = \{4,5\} and D = \{4,6\} intersecting at 4. No intersections occur between the pairs (e.g., A \cap C = \emptyset), yielding no additional edges; this illustrates how isolated components arise from disjoint intersection families.

History

Origins

The concept of intersection graphs emerged from early investigations into the intersection properties of set families within set theory and combinatorics during the 1930s and 1940s, particularly amid the development of topological structures and measurable sets in the Polish school of mathematics. These studies laid the groundwork for linking combinatorial relations to geometric and topological intersections. In 1945, Edward Szpilrajn-Marczewski formalized the connection between graphs and set intersections in his paper "Sur deux propriétés des classes d'ensembles," proving that every simple graph is the intersection graph of a family of sets.^[6] This result, achieved through a construction associating each vertex with a collection of sets such that edges correspond to nonempty intersections, arose in the context of general topology and properties of measurable sets.^[2] Marczewski's work provided the foundational observation that arbitrary graphs could be represented via set intersections, serving as the basis for the formal definition of intersection graphs. Following Marczewski's work, the framework extended to geometric graphs, with applications to map coloring problems where the dual graph models adjacency as intersections of regions on a plane. Initial motivations included representing geometric objects like curves or regions to capture adjacency and overlap in spatial configurations.

Key Developments

In 1957, Hugo Hadwiger and Hans Debrunner introduced a variant of Helly's theorem that generalized the intersection properties of convex sets in Euclidean space, laying foundational groundwork for the study of geometric intersection graphs. Their (p, q)-theorem posits that for families of compact convex sets in \mathbb{R}^d satisfying the condition that among any p sets, at least q intersect non-emptily (with p ≥ q ≥ d+1), there exists a bounded piercing number ensuring the entire family can be stabbed by a small number of points.^[7] This result established key Helly-type properties that characterize clique structures and dimensional constraints in the intersection graphs of such geometric objects, influencing subsequent characterizations of classes like convex position graphs. The term "intersection graph" was formally introduced in 1966 by Paul Erdős, Albert W. Goodman, and Lajos Pósa.^[8] That same year, they demonstrated that every graph on n vertices can be represented as the intersection graph of subsets chosen from a universe of at most \lceil n^2/4 \rceil elements.^[9] This bound on the intersection number provided the first quantitative insight into the representational efficiency of arbitrary graphs via set intersections, bridging combinatorial graph theory with intersection models and inspiring explorations of minimal universe sizes for specific graph classes. During the 1980s, Edward R. Scheinerman advanced axiomatic approaches to intersection graph classes through his doctoral work, developing frameworks for multiple intersection parameters and characterizing hereditary classes via intersection properties.^[10] His contributions, including theorems on the intersection dimensions of planar and other structured graphs, offered abstract conditions under which graphs admit representations from prescribed set families, such as intervals or disks, thereby unifying diverse subclasses under intersection-theoretic axioms. The period from the 1970s to the 1980s saw the evolution of intersection graph theory into specialized subclasses, notably string graphs—intersection graphs of simple curves in the plane—initially motivated by genetic mapping models and formalized in combinatorial contexts.^[11] These developments intertwined with perfect graph theory, as many intersection classes (e.g., interval and chordal graphs) were shown to be perfect, aligning with Berge's 1961 conjecture and fostering characterizations where forbidden subgraphs or ordering properties ensure optimality in coloring and clique covers. A comprehensive synthesis appeared in the 1999 monograph by Terry A. McKee and F. R. McMorris, which cataloged theoretical techniques across intersection graph types, emphasizing shared structural motifs and algorithmic implications.^[3]

Properties

All Graphs as Intersection Graphs

The Szpilrajn-Marczewski theorem, proved by Edward Marczewski in 1945, states that every simple undirected graph is the intersection graph of a family of sets.^[2] This result establishes that the class of intersection graphs encompasses all simple graphs, providing a universal representational framework within graph theory.^[1] A constructive proof proceeds as follows: For a graph G = (V, E) with |V| = n and |E| = m, let the universe be U = V \cup E. Assign to each vertex v \in V the set S_v = \{v\} \cup \{e \in E \mid e is incident to v\}. Then, for distinct vertices u, v \in V, the sets S_u and S_v intersect if and only if there exists an edge e = \{u, v\} \in E, which belongs to both S_u and S_v; otherwise, S_u and S_v share no elements, as the vertex labels differ and no common edges exist.^[12] This construction realizes G as an intersection graph over a universe of size n + m.^[1] Such representations require a universe of at least n elements in certain cases, such as the edgeless graph, where the corresponding sets must be pairwise disjoint and nonempty to reflect the absence of edges. Constructions like the one above use up to n + \binom{n}{2} elements, corresponding to the maximum possible edges in a simple graph.^[12] The theorem's universality implies that any graph-theoretic problem can be reformulated in terms of set intersections, facilitating connections to geometry, order theory, and combinatorics; for instance, it underpins the study of restricted intersection classes (e.g., interval or geometric graphs) as specializations of this general model.

Intersection Number

The intersection number of a graph G, denoted \theta(G), is the minimum cardinality of a ground set U such that G is the intersection graph of a family of subsets of U. That is, there exists an assignment of subsets S_v \subseteq U to each vertex v of G where S_u \cap S_v \neq \emptyset if and only if uv is an edge in G. This parameter measures the efficiency of representing G as an intersection graph, as smaller |U| implies a more compact universe for the subsets. Equivalently, \theta(G) is the clique edge-cover number of G, the minimum number of cliques in G needed to cover every edge of G at least once. Each element of U induces a clique consisting of all vertices whose subsets contain it, and these cliques collectively account for all edges. Erdős, Goodman, and Pósa established that for any graph G with n vertices, \theta(G) \leq \lfloor n^2/4 \rfloor, and this bound is tight. The complete bipartite graph K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil} achieves equality, as it is triangle-free and thus requires one clique (an edge) per edge to cover its \lfloor n^2/4 \rfloor edges. In general, for any triangle-free graph G, \theta(G) = |E(G)|, since the largest cliques are edges, each covering exactly one edge. Consequently, \theta(K_{m,n}) = mn for the complete bipartite graph K_{m,n}. For complete graphs, \theta(K_n) = 1, as the single clique consisting of all n vertices covers every edge. More broadly, \theta(G) \geq \nu(G), where \nu(G) is the matching number of G, because each clique can cover at most one edge from a maximum matching (as including two matching edges in a single clique would require additional edges between their endpoints). However, this bound is not tight in general, and tighter estimates depend on the structure of G. Computing \theta(G) exactly is NP-hard, even for restricted classes such as planar graphs and graphs with maximum degree 6. The problem remains APX-hard, meaning it is NP-hard to approximate within a constant factor, though polynomial-time heuristics and fixed-parameter tractable algorithms exist for certain parameterizations, such as when \theta(G) is small.^[14]

Classes of Intersection Graphs

Interval Graphs

Interval graphs are the intersection graphs formed by a collection of closed intervals on the real line, where each vertex represents an interval and an edge connects two vertices if and only if their intervals intersect. This class captures linear orderings and overlaps in one dimension, distinguishing it from higher-dimensional geometric intersection graphs.^[15] A graph is an interval graph if and only if it is chordal and contains no asteroidal triples. An asteroidal triple consists of three vertices such that for each pair, there exists a path connecting them that avoids the neighborhood of the third vertex. This structural characterization, established by Lekkerkerker and Boland, implies that interval graphs exclude induced cycles of length four or more (as a consequence of being chordal) along with specific other forbidden induced subgraphs, such as the claw (K_{1,3}) with certain attachments, the rising sun, and the umbrella. These forbidden subgraphs provide a finite list for recognition purposes.^[15] Interval graphs can be recognized in linear time through algorithms employing lexicographic breadth-first search (Lex-BFS), often combined with partition refinement techniques. In such an approach, multiple Lex-BFS orderings are computed to identify a clique chain—a linear ordering of maximal cliques where the cliques containing each vertex form a consecutive segment—verifying the interval property and enabling construction of an interval representation. Maximum cardinality search may complement this for initial chordality checks, but Lex-BFS is central to confirming the AT-free condition efficiently. As a subclass of chordal graphs, interval graphs are perfect, satisfying the condition that the chromatic number equals the clique number for every induced subgraph. Thus, for an interval graph G, χ(G) = ω(G), allowing optimal coloring via greedy algorithms along an interval ordering, where the minimum number of colors needed matches the size of the largest clique. Regarding the intersection number θ(G)—the minimum size of a ground set for a subset intersection representation—interval graphs satisfy θ(G) equal to the number of maximal cliques, which aligns with their perfectness in enabling efficient edge clique covers.^[15] In applications, interval graphs model scheduling tasks with time intervals, where non-overlapping intervals indicate compatible assignments; graph coloring then determines the minimum resources required, directly equaling the maximum overlap ω(G). Chordal graphs constitute a significant class of intersection graphs, specifically those that can be represented as the intersection graphs of subtrees in a tree. This characterization, established independently by several researchers in the early 1970s, highlights their structural connection to tree decompositions, where each vertex corresponds to a subtree and edges represent nonempty intersections between subtrees. A chordal graph admits such a representation if and only if it possesses a perfect elimination ordering (PEO), an ordering of vertices where, for each vertex, its neighbors that appear later in the ordering induce a clique. This ordering facilitates efficient algorithms for various graph problems on chordal graphs.^[16] Key properties of chordal graphs include the absence of induced cycles of length four or greater, ensuring that every cycle of length at least four contains a chord. Additionally, in chordal graphs, every minimal vertex separator is a clique, providing a structural basis for their elimination schemes and decompositions. These properties distinguish chordal graphs from more general classes and enable their role in optimization and sparse matrix computations. Recognition of chordal graphs can be performed in linear time using maximum cardinality search (MCS), an algorithm that iteratively selects the vertex with the maximum number of numbered neighbors to construct a potential PEO; verification confirms chordality if the ordering is perfect. This approach, building on lexicographic breadth-first search, runs in O(n + m) time for a graph with n vertices and m edges.^[16]^[17] Interval graphs form a proper subclass of chordal graphs, arising as those chordal graphs whose subtree intersection representation uses a path as the host tree, thereby restricting subtrees to intervals along a line.

Geometric Intersection Graphs

Geometric intersection graphs arise from the intersections of geometric objects embedded in the Euclidean plane or higher dimensions, where vertices represent these objects and edges connect pairs whose objects intersect. Prominent examples include unit disk graphs, which are the intersection graphs of disks of equal radius in the plane, modeling phenomena such as wireless network connectivity where nodes have uniform transmission ranges.^[18] Another key class is string graphs, formed by the intersections of continuous curves in the plane, which generalize segment intersection graphs and capture more complex topological interactions.^[19] These graphs exhibit diverse properties but are not necessarily perfect, as certain subclasses like grid intersection graphs—arising from horizontal and vertical line segments on a grid—can contain induced odd cycles longer than triangles, violating perfect graph criteria.^[20] Notably, geometric intersection graphs possess significant representational power; every finite planar graph can be realized as the intersection graph of straight-line segments in the plane. They relate closely to map graphs, which are intersection graphs of finitely many simply connected and internally disjoint regions in the plane, generalizing planar maps where adjacency occurs along shared boundaries.^[21] Characterizing geometric intersection graphs is computationally challenging in general. Recognizing unit disk graphs is NP-hard, a result stemming from the difficulty of determining whether a given graph admits a representation with unit disks without excessive overlaps. Similarly, recognition for general disk graphs and segment intersection graphs is NP-hard. However, polynomial-time algorithms exist for restricted cases, such as grounded segment graphs where one endpoint of each segment is fixed on a line, enabling efficient verification through dynamic programming.^[20] Forbidden subgraph characterizations remain limited for broad geometric classes; for instance, string graphs exclude certain minor-forbidden structures, but no complete set of forbidden subgraphs is known, complicating recognition further.^[19]

Recognition and Algorithms

Recognition Problems

The recognition problem for intersection graphs asks whether a given undirected graph G = (V, E) admits a representation as the intersection graph of sets from a specified family \mathcal{F}, such as intervals on a line or disks in the plane.^[22] This decision problem varies significantly in computational complexity depending on the family \mathcal{F}, with some classes admitting efficient algorithms while others are intractable. For interval graphs, where \mathcal{F} consists of intervals on the real line, recognition can be performed in linear time O(|V| + |E|) using lexicographic breadth-first search (Lex-BFS) to verify the characterization as chordal graphs without asteroidal triples.^[23] Similarly, chordal graphs, which are intersection graphs of subtrees of a tree, can be recognized in linear time O(|V| + |E|) via maximum cardinality search (MCS) to find a perfect elimination ordering. Circle graphs, intersection graphs of chords of a circle, also admit polynomial-time recognition, with a near-linear time algorithm running in O((|V| + |E|) \alpha(|V| + |E|)) time, where \alpha is the inverse Ackermann function, based on overlap graph decompositions.^[24] In contrast, recognition is NP-complete for several important classes. Unit disk graphs, intersection graphs of equal-radius disks in the Euclidean plane, have NP-complete recognition, as shown by a reduction from 3-SAT that constructs a graph embeddable as unit disks if and only if the formula is satisfiable.^[25] String graphs, intersection graphs of simple Jordan curves in the plane, are also NP-complete to recognize; the NP-hardness follows from a reduction involving segment intersections, and membership in NP is established by bounding the number of crossings in a representing drawing.^[26] A key approach for recognizing certain classes relies on forbidden induced subgraphs or minors. For asteroidal triple-free (AT-free) graphs, which include interval graphs as the subclass of chordal AT-free graphs, recognition uses the absence of asteroidal triples—three vertices where each pair is connected by a path avoiding the neighborhood of the third. Polynomial-time algorithms exist for AT-free recognition, such as a O(|V|^3) dynamic programming method or faster variants using modular decomposition.^[27] Partial algorithms address intractability through fixed-parameter tractability (FPT). For map graphs, a subclass of string graphs representing planar region intersections, recognition is FPT when parameterized by treewidth k, with running time O(2^{O(k)} \cdot |V|) using bounded tree decomposition and dynamic programming.^[28] Similar FPT results hold for recognizing intersection graphs in other geometric families when restricted to bounded treewidth.^[29] Open problems persist for some classes, particularly those involving real-number coordinates. Recognition of intersection graphs of line segments in 3D space or certain circle orders is \exists\mathbb{R}-complete, placing it between NP and PSPACE in the polynomial hierarchy, with no known polynomial-time algorithm.^[30]

Computing Representations

Every graph admits an intersection representation, as established by the Szpilrajn-Marczewski theorem. A straightforward construction for arbitrary graphs with n vertices and m edges assigns a unique element to each edge, placing it in the sets corresponding to the two incident vertices; this yields a representation over a universe of size m ≤ n(n-1)/2 = O(n²) elements and can be computed in O(n²) time by iterating over the edges.^[9] An improved construction, using a covering of the edges by complete subgraphs, achieves a universe of size at most ⌊n²/4⌋, also implementable in O(n²) time via an inductive edge-clique covering procedure.^[9] For specific classes of intersection graphs, more efficient and structured representations can be computed. Interval graphs, for instance, can be represented by intervals on the real line. To construct such a representation, first test the adjacency matrix for the consecutive ones property using a linear-time algorithm based on PQ-trees, which permutes the rows so that the 1s in each column form a consecutive block.^[31] From this ordering, identify the maximal cliques (one per row transition) and assign interval endpoints to each vertex as the leftmost and rightmost clique positions it belongs to, yielding the explicit intervals in O(n + m) time.^[32] Geometric intersection graphs, such as disk graphs, pose greater challenges since exact recognition and representation construction are NP-hard. Approximation algorithms address this by computing embeddings that realize the graph (or a close approximation) with disks of bounded radius ratio. For unit disk graphs, greedy placement methods iteratively position disk centers to satisfy neighborhood constraints while minimizing violations, achieving polynomial-time approximations with constant stretch factors relative to the optimal radius. Optimizing the universe size in an intersection representation equates to minimizing the intersection number i(G), the smallest size of such a universe, which equals the minimum edge-clique cover number and is NP-hard to compute exactly. Formulations as integer linear programs model this as selecting a minimum set of cliques to cover all edges, solvable via branch-and-bound or cutting-plane methods for moderate-sized graphs; heuristics like greedy clique selection provide practical approximations.^[9] Software tools facilitate these computations for certain classes. The SageMath library includes functions to generate and recognize interval graphs from interval lists, constructing explicit representations via clique orderings.^[33] For visualization, Graphviz can render interval representations as horizontal bars aligned by endpoints, aiding verification. Specialized packages, such as those in NetworkX for graph analysis, support interval graph generation but require custom implementation for full representation construction from arbitrary interval graphs.^[34] Despite these advances, computing minimal representations remains challenging, requiring exponential time in general due to the NP-hardness of exact clique cover; even for restricted classes like general intersection graphs, optimal universe sizes demand exhaustive search or advanced solvers.

Applications

Combinatorial Optimization

Intersection graphs provide a powerful framework for modeling and solving combinatorial optimization problems, especially in resource allocation and scheduling, where conflicts between entities can be represented as intersections. In particular, specific classes of intersection graphs, such as interval and chordal graphs, leverage their structural properties to enable polynomial-time algorithms for otherwise NP-hard problems like graph coloring and independent set computation. Interval graphs are widely used in scheduling applications, where jobs or tasks are modeled as intervals on a timeline, and edges represent overlapping intervals that cannot be executed simultaneously due to non-overlap constraints. The problem of assigning resources or time slots to these jobs reduces to finding a proper vertex coloring of the interval graph, where the chromatic number equals the size of the maximum clique (the maximum number of overlapping intervals), allowing a greedy left-to-right coloring algorithm to optimally schedule the jobs in linear time. This approach ensures minimal resource usage, as the number of colors needed matches the peak overlap demand.^[35] In bioinformatics, interval graphs model overlapping intervals in DNA fragment assembly for genome sequencing or constraints in protein secondary structure prediction, where edges indicate compatible overlaps or interactions. These representations enable efficient algorithms for reconstructing sequences from partial reads or determining feasible folding configurations, as explored in early work on computer-assisted sequencing.^[1] Chordal graphs, another important class of intersection graphs, find applications in Bayesian networks for probabilistic inference, where the moral graph of the network is triangulated to form a chordal graph. A perfect elimination order in the chordal graph enables efficient message passing via the junction tree algorithm, reducing complex joint probability computations to local operations on cliques, which scales well for large networks in decision support systems. This method exploits the chordal structure to perform exact inference in time proportional to the treewidth of the graph. The intersection number of a graph, defined as the minimum size of a universe such that the graph is the intersection graph of subsets of that universe, models resource allocation problems where entities share a limited pool of resources, and intersections represent conflicts requiring distinct allocations. Minimizing the intersection number corresponds to finding the smallest set of resources that can resolve all conflicts, equivalent to covering the edges with the fewest cliques, which aids in optimizing bandwidth allocation or parallel processing schedules. In weighted variants of these problems, such as the maximum weight independent set on interval graphs, dynamic programming algorithms compute the optimal non-overlapping selection of intervals with maximum total weight in O(n) time, where n is the number of intervals, by processing them in endpoint order and maintaining states for inclusion decisions. This is particularly useful in selective scheduling, like prioritizing high-value jobs under capacity limits. A notable case study is in university timetabling, where courses or exams are represented as intervals, and conflicts (e.g., shared instructors or rooms) form an interval graph; coloring this graph assigns time slots efficiently, with the greedy algorithm guaranteeing optimality since the graph is perfect, thus minimizing the number of periods needed while satisfying all constraints.

Computational Geometry

Intersection graphs play a significant role in computational geometry, particularly in modeling geometric configurations that arise in practical applications such as wireless communication and cartography. One prominent example is the use of unit disk graphs to model wireless ad hoc networks, where vertices represent transmitters located at points in the plane, and edges connect pairs whose unit-radius disks intersect, corresponding to overlapping signal ranges. This model captures both coverage requirements and interference patterns, enabling analysis of network capacity and connectivity. In the seminal work on wireless network capacity, the protocol model—closely related to unit disk graphs—is used to derive scaling laws for throughput in dense networks, showing that per-node capacity decreases as the square root of the number of nodes due to interference constraints. Such graphs facilitate algorithms for topology control, where edges are selectively activated to minimize interference while maintaining connectivity, as explored in heuristics for independent set approximation in unit disk graphs.^[36] In cartography, string graphs, which are intersection graphs of continuous curves in the plane, are employed to model map labeling problems, where labels are represented as curves that must avoid unwanted intersections to ensure clarity. The goal is often to find a maximum independent set in the string graph, corresponding to the largest set of non-crossing labels placed alongside features like roads or boundaries. This application arises in computational cartography, where curve intersections model label overlaps that degrade map readability, and optimization techniques aim to maximize label placement without crossings. For instance, computing the independence number of string graphs provides bounds on the maximum number of labels that can be placed without intersection, directly impacting automated map generation systems. Intersection graphs of line segments find application in VLSI design, particularly for minimizing wire crossings and vias in multi-layer routing. Here, vertices represent wire segments on a layer, and edges indicate potential crossings if assigned to the same layer, forming a segment intersection graph. Minimizing vias—connections between layers—reduces manufacturing costs and improves signal integrity, and this is achieved by graph coloring or bipartitioning the intersection graph to assign segments to layers without crossings within each layer. Practical algorithms for constrained via minimization use the segment-crossing graph to model interactions, achieving efficient layer assignments for multi-layer boards. Proximity problems in computational geometry, such as nearest neighbor search, can be framed using special cases of intersection graphs, where proximity graphs like the Gabriel graph or relative neighborhood graph connect points based on empty intersection regions such as disks or lenses. These graphs serve as sparse spanners for the complete proximity graph, aiding in efficient querying for nearest neighbors amid point sets, with applications in clustering and facility location. The structure allows for approximations where edges correspond to non-intersecting dominance regions, enabling subquadratic-time algorithms for construction.^[37] Post-2000 developments have extended intersection graphs to robotics, particularly in path planning where obstacle intersections are modeled to ensure collision-free trajectories. In multi-robot systems, intersection graphs of potential path segments or expanded obstacle regions help identify feasible routes by representing conflicts as edges, facilitating decoupled planning that sequences motions to avoid simultaneous intersections. Recent convex optimization frameworks incorporate these graphs to compute safe paths around dynamic obstacles, enhancing real-time adaptability in environments like warehouses.^[38]

Containment Graphs

Containment graphs represent a distinct model from intersection graphs, where vertices correspond to sets and an edge between two vertices exists if one set properly contains the other, denoted as S_u \subset S_v or S_v \subset S_u. This contrasts with intersection graphs, where edges indicate non-empty overlap between sets. In the containment framework, the relation captures hierarchical inclusion rather than mere overlap, making it suitable for modeling nested structures such as organizational hierarchies or subset relations in data. Seminal work defines containment graphs as the comparability graphs of posets under containment orders, where the partial order is induced by proper set inclusion.^[39] For the specific case of intervals on the real line, containment graphs of intervals—where each vertex is assigned an interval and edges reflect proper containment of one interval within another—are precisely the comparability graphs of posets with dimension at most 2. This equivalence stems from the fact that such posets can be realized by two linear extensions without conflicts in ordering, aligning with the nested structure of intervals. Unlike standard interval intersection graphs, which model overlapping intervals and form a chordal graph class, interval containment graphs emphasize strict nesting and inherit the perfect graph properties of comparability graphs. These graphs are used in applications requiring hierarchical representations, differing from the overlap-focused modeling in intersection graphs.^[40]^[39] Every containment graph is an intersection graph, as they coincide with the intersection graphs of subtrees in a tree, where edges represent shared subtrees. However, the converse does not hold; not every intersection graph is a containment graph. For example, induced cycles of length 4 or more, such as C_4, can be realized as intersection graphs of certain geometric objects like boxes or arcs but are not comparability graphs, hence not containment graphs, due to the lack of a transitive orientation. The forbidden induced subgraphs for containment graphs thus include those that violate comparability, such as odd holes (induced odd cycles of length at least 5) and their complements, differing from the forbidden structures in broader intersection classes, which may permit such cycles.^[39] Recognition of interval containment graphs is achievable in polynomial time, leveraging algorithms for determining if a comparability graph arises from a poset of dimension at most 2, which can be tested via transitive orientation and linear extension checks. This polynomial-time solvability contrasts with the NP-completeness of recognizing containment graphs for higher-dimensional boxes, such as in 2D or above. These algorithmic differences highlight the structural constraints imposed by the containment model compared to general intersection representations.^[41]^[39]

Graph Dimensions

The boxicity of a graph G, denoted \operatorname{box}(G), is the minimum integer k such that G is the intersection graph of k interval graphs on the same vertex set; equivalently, it is the smallest dimension k in which G can be represented as the intersection graph of axis-aligned boxes in \mathbb{R}^k.^[42] This parameter, introduced by F. S. Roberts in 1969, measures how "interval-like" a graph is by requiring multiple interval representations whose common edges define G.^[43] Roberts characterized graphs of boxicity at most k through this intersection property and proved that \operatorname{box}(G) \leq \lfloor n/2 \rfloor for any n-vertex graph G, establishing an upper bound on the complexity.^[44] Notably, \operatorname{box}(G) = 1 if and only if G is an interval graph.^[43] Computing the boxicity of a graph is NP-hard, even for fixed small values like k=2 or k=3.^[44] One approach to determining boxicity involves representing the graph via containment orders: specifically, \operatorname{box}(G) equals the minimum k such that the complement \overline{G} can be expressed as the union of k comparability graphs of interval orders, linking it to order-theoretic dimensions.^[45] This connection underscores boxicity's role in generalizing one-dimensional interval representations to higher dimensions through iterative intersections. An analogous parameter is the track number, defined as the minimum integer k such that G is the intersection graph of paths on k parallel tracks (monotone paths connecting points on ordered tracks), which equivalently means G is the union of k interval graphs.^[46] Introduced by Győri, Kostochka, and Luczak in the context of multitrack intervals, the track number captures path-based generalizations similar to boxicity's interval-based ones, with applications in graph drawing and layout where paths simulate edge routings across tracks.^[46] For example, every planar graph has track number at most 225.^[47] These dimension parameters extend to broader generalizations, such as the product of graphs (where the Cartesian product of interval graphs yields higher-dimensional analogs) or cubicity, the minimum k for intersection graphs of k-dimensional cubes, also defined by Roberts in 1969 as a stricter higher-dimensional variant of boxicity.^[44] Such extensions highlight how intersection graph dimensions quantify representational complexity across geometric and order-based structures.

References

[1]
[PDF] Intersection Graphs: An Introduction - arXiv
Oct 1, 2013 · Depending on the geometrical representation, different type of intersection graphs are defined. Among them interval, circular-arc, permutation, ...
[2]
Topics in Intersection Graph Theory - SIAM Publications Library
This book is the only source for an extended, concentrated focus on the theory and techniques common to various types of intersection graphs.Missing: key | Show results with:key
[3]
A Characterization of Comparability Graphs and of Interval Graphs
Nov 20, 2018 · A graph G with vertices P for which there exists a partial ordering < such that G = G(P, <) is called a comparability graph.
[4]
Algorithmic Graph Theory and Perfect Graphs - ScienceDirect.com
Algorithmic Graph Theory and Perfect Graphs provides an introduction to graph theory through practical problems. This book presents the mathematical and ...
[5]
Sur deux propriétés des classes d'ensembles - EuDML
Szpilrajn-Marczewski, Edward. "Sur deux propriétés des classes d'ensembles." Fundamenta Mathematicae 33.1 (1945): 303-307. <http://eudml.org/doc/213098> ...
[6]
[PDF] A Translation of Sur deux propriétés des classes d'ensembles by ...
Jun 25, 2009 · Edward Szpilrajn-Marczewski's Sur deux propriétés des classes d'ensembles is a text much refer- enced in intersection graph theory, since ...
[7]
The Representation of a Graph by Set Intersections
Nov 20, 2018 · A graph is a collection of points (vertices) and edges (curves) joining two distinct vertices, with no more than one edge between two vertices.
[8]
[PDF] INTRODUCTION TO RANDOM GRAPHS
Sep 1, 2025 · example, interval graphs defined as the intersection graphs of intervals on the real line, unit disc graphs defined as the intersection ...<|control11|><|separator|>
[9]
Über eine Variante zum Hellyschen Satz | Archiv der Mathematik
Hadwiger, H., Debrunner, H. Über eine Variante zum Hellyschen Satz. Arch. Math 8, 309–313 (1957). https://doi.org/10.1007/BF01898794
[10]
[PDF] THE REPRESENTATION OF A GRAPH BY SET INTERSECTIONS
A graph can be represented by sets where vertices are associated with sets, and edges exist if the intersection of two sets is not empty. A graph with n ...
[11]
ISGCI References 900 - 999 - Graph Classes
954, E.R. Scheinerman Intersection classes and multiple intersection parameters of a graph. Ph. D. Thesis, Princeton University 1984 ; 955, E.R. Scheinerman
[12]
[PDF] String graphs and incomparability graphs - MIT Mathematics
The intersection graph of a collection C of sets has vertex set C and two sets in C are adjacent if and only if they have nonempty intersection. A curve is a ...
[13]
[PDF] Intersections and Representations of Graphs - Clemson OPEN
In intersection graph theory, the vertices of a graph are usually represented by the members of some family F of sets (often, the set [k] = {1, 2,...,k}, for ...
[14]
[PDF] Algorithmic Aspects of the Intersection and Overlap Numbers ... - HAL
Aug 10, 2014 · Erdös, A.W. Goodman, and L. Pósa, The intersection of a graph by set intersections, Canad. J. Math. 18 (1966), 106–112. 6. J. Gramm, J. Guo ...Missing: n²) | Show results with:n²)
[15]
Representation of a finite graph by a set of intervals on the real line
Lekkeikerker, C., and Boland, J.. "Representation of a finite graph by a set of intervals on the real line." Fundamenta Mathematicae 51.1 (1962): 45-64.Missing: original | Show results with:original
[16]
Algorithmic Aspects of Vertex Elimination on Graphs
We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear ...
[17]
[PDF] Maximum Cardinality Search and Chordal Graphs
Theorem 1. Performing a maximum cardinality search on a graph G produces a simpli- cial elimination ordering for G if and only if G is chordal.
[18]
chordal - Graph Classes
A graph G is chordal if it is the intersection graph of subtrees of a tree T. In particular T can be chosen such that each node of T corresponds to a maximal ...
[19]
graph theory - Relation between tree-width and clique number
May 9, 2014 · 9. tw(G)=ω(G)−1 for chordal graphs. · since treewidth is closed under taking subgraphs, if a graph G has Kn as subgraph then the treewidth of G ...
[20]
[PDF] UNIT DISK GRAPHS 1. Preliminaries - Computer Science Department
Unit disk graphs are the intersection graphs of equal sized circles in the plane: they provide a graph-theoretic model for broadcast.
[21]
[PDF] Geometric Intersection Patterns and the Theory of Topological Graphs
In this section, we would like to illustrate by an example how questions about topological graphs lead to the study of intersection graphs of geometric objects.<|control11|><|separator|>
[22]
Tractabilities and Intractabilities on Geometric Intersection Graphs
A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and ...
[23]
Map graphs | Journal of the ACM
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not ...
[24]
Graph Classes: A Survey | SIAM Publications Library
Graph Classes: A Survey. Author(s):. Andreas Brandstädt,; Van Bang Le, and ... Intersection graphs (see Definition 1.2.3) are a very general notion in ...
[25]
The ultimate interval graph recognition algorithm?
Our main contribution is to exhibit a very simple, linear- time, recognition algorithm for interval graphs involving four sweeps of the we&known Lexicographic ...
[26]
Unit disk graph recognition is NP-hard - ScienceDirect.com
Unit disk graphs are the intersection graphs of unit diameter closed disks in the plane. This paper gives a polynomial-time reduction from SATISFIABILITY to the ...
[27]
Recognizing string graphs in NP - ScienceDirect
A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that ...
[28]
Recognizing graphs without asteroidal triples - ScienceDirect.com
In this paper we study the recognition problem of AT-free graphs from different perspectives and present three different recognition algorithms for AT-free ...
[29]
Recognizing Map Graphs of Bounded Treewidth - DROPS
Jun 22, 2022 · We present an explicit fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. The algorithm has time ...
[30]
Recognizing Map Graphs of Bounded Treewidth | Algorithmica
Oct 27, 2023 · We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph.
[31]
The Complexity of Intersection Graphs of Lines in Space and Circle ...
Jun 25, 2024 · We prove that the recognition problems for intersection graphs of lines and circle orders are both exists\mathbb{R}-complete, hence polynomial-time equivalent.
[32]
https://ic.unicamp.br/~meidanis/courses/mo640/2006s1/textos/Booth-Lueker-1975.pdf
[33]
[PDF] Linear Algorithms to Recognize Interval Graphs and - IC-Unicamp
Abstract. A matrix of zeroes and ones is said to have the consecutive ones property if there is a permutation of its rows such that the.
[34]
Intersection number (graph theory) - Wikipedia
^ Jump up to: Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of ...Missing: n²) | Show results with:n²)
[35]
Intersection graphs - Graph Theory
An interval graph is built from a list ( a i , b i ) 1 ≤ i ≤ n of intervals : to each interval of the list is associated one vertex, two vertices being adjacent ...
[36]
interval_graph — NetworkX 3.5 documentation
In graph theory, an interval graph is an undirected graph formed from a set of closed intervals on the real line, with a vertex for each interval and an edge ...Missing: representation | Show results with:representation
[37]
[PDF] Interval Scheduling: A Survey
Apr 21, 2006 · It is well known that interval scheduling problems and interval graphs are related. Indeed, the graph that arises when there is a node for each.
[38]
Simple heuristics for unit disk graphs - Marathe - Wiley Online Library
We present simple and provably good heuristics for a number of classical NP-hard optimization problems on unit disk graphs.
[39]
[PDF] 32 PROXIMITY ALGORITHMS - CSUN
Let V be a finite set in the Euclidean plane. The nearest neighbor graph NNG(V ) connects each point in V to its nearest neighbor. It is usually defined as a di ...
[40]
Motion planning around obstacles with convex optimization - Science
Nov 15, 2023 · We present a framework that enables convex optimization to efficiently and reliably plan trajectories around obstacles.
[41]
[PDF] Containment Graphs, Posets, and Related Classes of Graphs - arXiv
In this paper we introduce the notion of the containment graph of a family of sets and containment classes of graphs and posets.
[42]
[PDF] Partially Ordered Sets
Mar 23, 2013 · Partially Ordered Sets. Author(s): Ben Dushnik and E. W. Miller. Source: American Journal of Mathematics, Vol. 63, No. 3 (Jul., 1941), pp. 600- ...
[43]
TRANSITIVE ORIENTATION OF GRAPHS AND IDENTIFICATION ...
Introduction. The graphs considered in this paper are assumed to be finite, with no edge joining a vertex to itself and with no two distinct edges.
[44]
Boxicity and Maximum Degree (2008)
The boxicity of a graph G, written box(G) and introduced by Roberts [R], is the minimum number of interval graphs with vertex set V(G) whose intersection is G.
[45]
[PDF] Boxicity of graphs with bounded degree
Mar 20, 2008 · The boxicity of a graph G can be equivalently defined as the smallest k such that G is the intersection of k interval graphs. Graphs with ...
[46]
[PDF] Parameterized Algorithms for Boxicity - Rajesh Chitnis
The boxicity of a graph G, denoted box(G), is the minimum integer k such that G has a k-box representation. Boxicity was introduced by Roberts. [31] in 1969 and ...
[47]
[PDF] Boxicity, poset dimension, and excluded minors
Apr 12, 2018 · The boxicity box(G) of a graph G, introduced by Roberts [19], is defined as the smallest k such that. G is the intersection of k interval ...<|control11|><|separator|>
[48]
[PDF] MULTITRACK INTERVAL GRAPHS
The multitrack interval number or simply track number of a graph G is the minimum number of interval graphs whose union is G. The track number for K m,n is ...