Abstract
The problem of extending partial geometric graph representations, such as plane graphs, has gained significant traction in recent years. While extending planar drawings is solvable in linear time, the problem becomes considerably more complex for "beyond-planar" classes. This paper addresses the extension problem for 1-planar drawings—drawings where each edge is allowed at most one crossing. We demonstrate that if a partial drawing $\mathcal{H}$ of a connected subgraph $H$ is given, it can be extended to a 1-planar drawing of the full graph $G$ in polynomial time, provided that $G$ is obtained from $H$ by deleting a bounded number of vertices and edges.
The Extension Problem in Graph Drawing
In graph drawing, the extension problem asks a fundamental question: given a graph $G$, a subgraph $H$, and a fixed drawing $\mathcal{H}$ of $H$, can we complete the drawing for the entirety of $G$ while maintaining a specific topological property?
For planar drawings, where no edges are permitted to cross, this was solved in linear time by Angelini et al. (2015). However, many real-world networks are inherently non-planar. This has led researchers to explore 1-planar drawings. While recognizing 1-planar graphs is generally NP-complete, recent breakthroughs showed that the extension problem is solvable in polynomial time if only a few edges are missing. The major open question, which this work resolves, is whether polynomial-time solvability holds when vertices are also missing. Deleting a vertex can remove an arbitrary number of incident edges, significantly increasing the complexity of the "gap" between the partial and full drawing.
A Constructive Algorithmic Framework
The authors propose a sophisticated constructive algorithm that determines if an extension exists and, if so, computes the coordinates and crossing points. The algorithm follows a multi-stage approach:
- Initial Branching: Since the number of missing elements ($\kappa$) is small and the existing subgraph $H$ is connected, the algorithm can exhaustively "guess" which regions (cells) of the current drawing the new vertices should inhabit.
- Bounding Crossings: A key technical lemma proves that in any valid extension, the number of crossings between pairs of newly added edges is bounded by a function of $\kappa$. This allows the algorithm to branch on all possible crossing configurations for these new edges.
- Decomposition into Base Regions: The paper introduces "base regions"—parts of the plane associated with specific missing vertices. By partitioning the drawing's cells, the global problem is decomposed into independent local routing subproblems.
- Dynamic Programming (Delimit-and-Sweep): To solve the final subproblem—routing edges between vertices through a series of cells—the authors use a "delimit-and-sweep" DP approach. This involves moving a "delimiter" curve across the drawing to update a table of reachable states.
Theoretical Foundations: Connectivity and Laminarity
The success of this algorithm hinges on two critical observations:
- The Role of Connectivity: The assumption that the partial subgraph $H$ is connected is vital. It provides a rigid "skeleton" that constrains the possible locations of new edges and limits their crossing patterns. Without this connectivity, the search space for crossing configurations would become unmanageable.
- Laminar Structures: The authors observe that when new edges do not cross each other (the "untangled" phase), their interactions with cell boundaries form a "laminar" (nested) structure. This structural property is what makes the dynamic programming approach computationally feasible.
Key Results and Complexity
The primary contribution is Theorem 1, which establishes that for a fixed constant $\kappa$, it is possible to determine if a 1-planar drawing $\mathcal{H}$ of a connected subgraph $H$ can be extended to $G$ in polynomial time.
The algorithm's running time is $n^{O(\kappa^{28})}$. While the high exponent makes this a "theoretical" polynomial time, it is a landmark result that proves the problem is not NP-hard under these constraints. Furthermore, the algorithm is constructive, providing the actual drawing rather than just a decision.
Conclusion and Future Directions
This work bridges a significant gap in graph drawing theory by extending the reach of polynomial-time extension algorithms to 1-planar representations with missing vertices. However, several challenges remain:
- Connectivity: The current techniques rely heavily on $H$ being connected. Extending this to disconnected subgraphs remains an open problem.
- Efficiency: Investigating whether the problem is Fixed-Parameter Tractable (FPT) could lead to more practical algorithms where the complexity depends more gracefully on $\kappa$.
- Generalization: The "delimit-and-sweep" and decomposition methods might serve as a template for extension problems in other "beyond-planar" classes, such as $k$-planar or fan-planar graphs.
Summary updated