The Complexity of Geometric Graph Recognition

67 concepts39 papers1 proposal

An abstract graph is a purely combinatorial object—a set of vertices connected by edges. However, many graphs encountered in practice possess an underlying geometric structure. For instance, an intersection graph represents vertices as geometric shapes (such as disks, intervals, or polygons) where an edge exists if and only if their corresponding shapes overlap. Similarly, beyond-planar graphs extend classical planarity by allowing edges to cross only under strict topological rules, such as permitting at most one crossing per edge (1-planarity).

A major motivation for studying these geometric classes is that their rich structural properties often make otherwise intractable problems easy. For example, finding the maximum clique in a general graph is a classic NP-hard problem. Yet, as shown by Brimkov et al. in Homothetic polygons and beyond: Maximal cliques in intersection graphs, if an intersection graph is formed by convex polygons whose sides are restricted to a fixed number of directions, the number of maximal cliques is polynomially bounded. This structural guarantee collapses the complexity of the Maximum Clique problem down to polynomial time.

But this algorithmic shortcut comes with a catch: to exploit these geometric properties, we must first know whether an arbitrary abstract graph actually belongs to the geometric class in question. This is the recognition problem. Unfortunately, determining whether a graph can be geometrically realized is frequently an NP-hard, or even undecidable, challenge.

Why Geometric Recognition is Hard

The fundamental difficulty of geometric graph recognition stems from a tension between discrete combinatorics and continuous geometry. When we attempt to embed a graph into a geometric space, a local choice—such as placing a polygon or routing a crossing edge—propagates constraints globally across the entire system.

Consider what happens when we try to represent a graph using simple polygons. Kratochvíl et al. demonstrate in Two Results on Intersection Graphs of Polygons that representing an abstract graph of $n$ vertices can force the polygons to become highly complex, requiring nearly $n$ corners. They prove that deciding whether a graph can be represented by polygons with a fixed number of corners $k$ is NP-complete for any $k \geq 3$.

Even when the geometric primitives are constrained to a grid, small changes in the allowed degrees of freedom trigger computational intractability. In Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill, Chaplick et al. analyze graphs formed by intersecting paths on a grid where each path can have at most $k$ bends ($B_k$-VPG graphs). They show that recognizing these graphs is NP-complete, even if you are already handed a valid representation that uses just one additional bend ($k+1$). The boundary between these classes is so rigid that knowing a nearby geometric layout does not simplify the task of finding a more constrained one.

Discrete Graph Structure          Continuous Geometric Realization
     (Vertices & Edges)               (Global Layout Constraints)

        A --- B --- C                  [ Shape A ] overlaps [ Shape B ]
         \   /   /                       but MUST NOT touch [ Shape C ]
          \ /   /                      
           D ---                       Every local placement propagates
                                       rigid geometric constraints globally.

For some geometric primitives, the recognition problem escapes the boundaries of standard NP-completeness entirely. In Intersection Graphs of Rays and Grounded Segments, the authors establish that recognizing intersection graphs of rays is complete for the existential theory of the reals ($\exists\mathbb{R}$). This means the problem is structurally tied to the complexity of deciding systems of polynomial inequalities over real numbers. In an earlier foundational result, Kratochvíl notes in Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane that for general string graphs, it was long an open question whether a finite recognition algorithm even existed, highlighting that geometric realization can verge on the undecidable.

Mapping the Tractability Frontier

To bypass this pervasive hardness, researchers look for the exact boundaries where the recognition problem transitions from intractable to solvable. This frontier is mapped by introducing topological constraints or structural parameters.

1. Fixed Rotation Systems

In graph drawing, a rotation system specifies the cyclic (clockwise) order of edges around each vertex. In the wild, this order is unknown, leaving an exponential number of combinatorial configurations to search through. However, if the rotation system is provided as part of the input, the problem becomes significantly more constrained.

In Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time, Eades et al. exploit this constraint. While general 1-planarity testing is NP-complete, they show that testing whether a graph is maximally 1-planar becomes solvable in linear time ($O(n)$) when the rotation system is fixed. The fixed edge ordering allows the algorithm to locally verify crossing configurations without worrying about global topological cascading.

However, a fixed rotation system is not a universal remedy. Bekos et al. demonstrate in On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs that recognizing fan-planar graphs remains NP-hard even when the rotation system is completely specified. This reveals that the combinatorial constraints inherent to fan-planarity are fundamentally more rigid than those of maximal 1-planarity.

2. Structural Subclasses and Boundary Reductions

Another strategy simplifies the problem by restricting the abstract structure of the input graph or the target drawing zone.

  • Outer-structures: If we mandate that all vertices must lie on the outer boundary of the drawing, the topological space collapses from a full plane to a single cyclic boundary. Hong et al. leverage this in A Linear-Time Algorithm for Testing Outer-1-Planarity, providing a linear-time recognition algorithm for outer-1-planar graphs, bypassing the NP-completeness of the unconstrained 1-planar class.
  • Property Collapsing: Sometimes, restricting the graph's combinatorial properties causes the geometric class to collapse into a simpler one. In Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane, Kratochvíl proves that while recognizing noncrossing arc-connected graphs is generally hard, the problem becomes trivial for triangle-free graphs because they are always planar.

3. Parameterized Complexity

When an exact polynomial-time algorithm is out of reach for general graphs, Fixed-Parameter Tractability (FPT) offers a way forward. Instead of measuring complexity solely by the total graph size $n$, FPT algorithms isolate the exponential explosion to a specific structural parameter $k$.

This approach is highly effective for layout extension problems. In Extending Partial 1-Planar Drawings, Eiben et al. study the problem of taking an already embedded partial graph and trying to draw the remaining missing pieces without violating 1-planarity. While this is NP-complete in general, they show it is FPT when parameterized by the number of missing vertices and edges. Similarly, Chaplick et al. provide the first FPT algorithms for upward planarity testing in Parameterized Algorithms for Upward Planarity by parameterizing by the number of source vertices or the graph's treedepth.

By isolating the source of geometric conflict to these small parameters, these algorithms demonstrate that the global complexity of geometric graph recognition can often be tamed in practical, highly structured scenarios.

Key Foundational Work

Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane (1996) — contributed 3 concept elements to this direction.
Grid Intersection and Box Intersection Graphs on Surfaces (Extended Abstract) (1995) — contributed 2 concept elements to this direction.
Simple heuristics for unit disk graphs (1995) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_intersection_graph_recognition_a1cdaf84,
  title = {intersection graph recognition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intersection-graph-recognition/rdr_a1cdaf848481434f80a977b8aaaf7a7e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_intersection_graph_recognition_a1cdaf84_v1,
  title = {intersection graph recognition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intersection-graph-recognition/rdr_a1cdaf848481434f80a977b8aaaf7a7e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake