Graph Drawing Under Fixed and Partial Embedding Constraints

20 concepts16 papers1 proposal

When we think about drawing a graph cleanly—minimizing crossings, keeping edges straight, or aligning vertices to a grid—we usually assume complete freedom over the layout. In a purely variable embedding setting, an algorithm can flip, spin, and reorder components at will to satisfy geometric constraints. However, real-world applications and deep theoretical questions often introduce constraints that lock parts of the graph in place.

This research direction explores the profound computational shift that occurs when transitioning from flexible layouts to fixed or partial embeddings. A fixed embedding predetermines the cyclic order of edges around every vertex (a rotation system) or the arrangement of faces, while a partial embedding anchors specific subgraphs or vertices to exact coordinates. Intuitively, these constraints act as a double-edged sword: they drastically prune the combinatorial search space, but they also strip away the topological flexibility needed to avoid crossings or geometric conflicts.

When Constraints Simplify: Pruning the Search Space

To understand why fixed embeddings can be beneficial, consider the problem of planarity or near-planarity testing. When a graph's embedding is completely variable, an algorithm must evaluate an exponential number of ways to arrange the edges around each vertex.

Locking down these choices simplifies the problem by providing a rigid topological template. For instance, testing whether a graph is "1-planar" (drawable with at most one crossing per edge) is generally NP-complete. However, Peter Eades et al. demonstrated that if a graph is provided with a pre-defined rotation system, testing for maximal 1-planarity can be achieved in linear time.

Similarly, in the context of directed graphs, Lukas Barth et al. showed that finding a planar upward drawing is computationally efficient when the combinatorial embedding is fixed, whereas the problem becomes NP-complete if the algorithm is allowed to rearrange the edge order.

This tractability extends to complex structural layouts. For example, Vít Jelínek et al. developed a polynomial-time algorithm for testing the "clustered planarity" (c-planarity) of graphs with a fixed plane embedding, even when clusters are fragmented into two components. The fixed embedding eliminates the chaotic freedom of component placement, allowing deterministic path-finding strategies to succeed.

The Paradox of Rigidity: When Constraints Induce Hardness

If fixing an embedding simplifies the combinatorial search, why does it sometimes make problems harder? The answer lies in the loss of topological flexibility. In a variable embedding, if two edges cross illegally, the algorithm can simply permute the cyclic order of edges around a vertex to "untangle" them. A fixed rotation system completely removes this escape hatch.

Michael A. Bekos et al. exposed this paradox by showing that recognizing fan-planar graphs becomes NP-hard precisely when the edge order around vertices is fixed. Without the freedom to reorder edges, satisfying strict crossing rules becomes a rigid puzzle where a single local mismatch can ruin the entire layout.

Even when a fixed rotation system reduces the topological search, the remaining geometric constraints can still be insurmountable. Paul Jungeblut settled a long-standing question by proving that finding a Lombardi drawing (where edges are smooth circular arcs meeting at equal angles) remains $\exists\mathbb{R}$-complete even with a fixed rotation system. The combinatorial problem is solved, but the underlying system of polynomial equations over real numbers remains highly complex.

Partially Embedded Graphs and Spatial Anchoring

A more severe constraint occurs when a portion of the graph is already drawn in the plane, and the goal is to complete the drawing without introducing crossings. Standard planarity algorithms fail here because they rely on flipping or rearranging components—actions that would violate the pre-existing spatial layout.

To address this, Patrizio Angelini et al. introduced a linear-time algorithm to test whether a partially embedded graph (PEG) can be extended to a full planar drawing. To provide a structural foundation for this problem, Jan Kratochvíl et al. established a Kuratowski-type theorem for PEGs, identifying the exact forbidden substructures (obstructions) that prevent a partial drawing from being completed.

When vertices are anchored to specific coordinates or restricted within boundaries, the problem shifts from pure topology to rigid geometry:

  • Bounded Movement: Patrizio Angelini et al. studied the Anchored Graph Drawing problem, proving that finding crossing-free layouts when vertices can only move a bounded distance from initial positions is NP-hard for most metrics.
  • Fixed Coordinates: Anupam Gupta et al. demonstrated that anchoring specific nodes at pre-assigned coordinates disrupts traditional continuous mapping strategies (like space-filling curves) used to minimize edge stretch.
  • Boundary Constraints: Anna Lubiw et al. proved that drawing a planar graph inside a polygonal region with boundary-fixed vertices is $\exists\mathbb{R}$-complete, showing that such rigid constraints can even force internal vertices to require irrational coordinates.

Geometric Consequences: Slopes, Crossings, and Visibility

The tension between fixed embeddings and geometric realization also manifests in edge styles, slope counts, and visibility representations. For instance, while any planar graph can be drawn with straight lines, doing so while preserving a specific set of crossings is much harder. Seok-Hee Hong et al. developed a linear-time algorithm to determine if a 1-planar graph can be re-embedded into a straight-line drawing while strictly preserving its existing crossing pairs, highlighting how a fixed crossing configuration restricts geometric options.

Similarly, when drawing graphs with a limited number of slopes, Vít Jelínek et al. noted that fixed plane embeddings impose significantly stricter constraints on edge placement than flexible ones, making it harder to find valid representations within a bounded set of directions. In visibility representations, Therese Biedl et al. showed that mapping a graph to an integral unit bar-visibility layout depends heavily on whether the embedding is fixed (providing a clear template) or variable (requiring an exhaustive search over edge orderings).

Finally, when trying to "untangle" a messy layout, Sujoy Bhore et al. showed that restoring planarity to a circular drawing by moving the minimum number of vertices is NP-complete. The fixed circular geometry limits the available positions, creating intricate dependencies where moving one vertex to fix a crossing inevitably creates others. This rigidity even impacts theoretical proofs; as Lutz Oettershagen et al. observed, many classic proofs in graph drawing rely on a globally fixed reference face, a constraint that limits our ability to analyze more flexible, complex embeddings.

Key Foundational Work

Clustered Planarity: Embedded Clustered Graphs with Two-Component Clusters (2008) — contributed 2 concept elements to this direction.
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree (2009) — 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_global_reference_face_constraint_6ced6a20,
  title = {global reference face constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-reference-face-constraint/rdr_6ced6a2005584a858379a7e71f3cec9b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_reference_face_constraint_6ced6a20_v1,
  title = {global reference face constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-reference-face-constraint/rdr_6ced6a2005584a858379a7e71f3cec9b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake