Extending Nearly Complete 1-Planar Drawings in Polynomial Time

Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Figure 1: A schematic representation of routing multiple edges between vertices $v$ and $w$ through a series of intermediate regions or interfaces.

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

Abstract

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph $G$, a connected subgraph $H$ of $G$ and a drawing $\mathcal{H}$ of $H$, the extension problem asks whether $\mathcal{H}$ can be extended into a drawing of $G$ while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when $H$ can be obtained from $G$ by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm.
BibTeX
@inproceedings{eiben2020extending,
  author = {Eduard Eiben and Robert Ganian and Thekla Hamm and Fabian Klute and Martin Nöllenburg},
  title = {{Extending Nearly Complete 1-Planar Drawings in Polynomial Time}},
  booktitle = {MFCS},
  year = {2020},
  doi = {10.4230/lipics.mfcs.2020.31},
}
Figure