Source-linked AI summary
A Survey on Graph Drawing Beyond Planarity
Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani
TL;DR
Non-planar graph drawings may be better understood by the properties of their crossings rather than crossing count alone. This survey classifies forbidden crossing configurations, synthesizes major results and relationships among beyond-planar families, and highlights unresolved theoretical and empirical questions.
Problem
The field needs a systematic account of forbidden crossing configurations, research directions, established results, and open problems in beyond-planar graph drawing.
Method
The survey develops a taxonomy of beyond-planar graph families and organizes combinatorial, algorithmic, relational, and experimental findings around it.
Results
Crossing geometry affects readability: eye-tracking evidence reports good readability for crossing angles from about π/3 to π/2, while the survey also synthesizes major family relationships and results.
Takeaways & Limitations
The survey presents beyond-planar drawing as a research area connecting crossing-aware models, structural results, algorithms, and user-centered evaluation.
Takeaways & Limitations
User studies assessing the practical effectiveness of beyond-planar models remain generally lacking, including for a recently introduced orthogonal PED variant.
Abstract
from arXiv · showhide
Graph Drawing Beyond Planarity is a rapidly growing research area that classifies and studies geometric representations of non-planar graphs in terms of forbidden crossing configurations. Aim of this survey is to describe the main research directions in this area, the most prominent known results, and some of the most challenging open problems.
1 Introduction
Graph drawing beyond planarity studies non-planar representations by considering the topological and geometric properties of crossings, not only their number. This survey classifies the area’s research directions, summarizes results, and identifies open problems.
- Crossing properties can affect readability beyond crossing count: an anecdotal study preferred a drawing with 41% more crossings but skewness four.The comparison suggests that topological crossing structure may matter more than the number of crossings alone.
- Eye-tracking experiments found that acute-angle crossings significantly impair understanding, whereas angles from about π/3 to π/2 support good readability.
- These findings motivate classifying non-planar graph drawings by forbidden crossing configurations and studying the resulting beyond-planar graph families.
- The survey asks which forbidden configurations and research directions define the field, what combinatorial and algorithmic results are known, and which problems remain open.
- It organizes the literature around a taxonomy and uses dedicated sections to review definitions, results, algorithms, and open problems.
2 Basic definitions on Graph Drawing
The paper defines drawings as vertex-point and edge-arc representations in the plane, together with crossings, faces, embeddings, and polyline complexity. It distinguishes planar, straight-line, and bent representations using standard topological terminology.
- A drawing maps vertices to distinct plane points and edges to simple Jordan arcs, with crossings defined as common points other than endpoints.
- Faces are the connected regions of a drawing, with the unbounded region called the external face; an embedding is an equivalence class of drawings under plane homeomorphism.
- A planar drawing has no crossings, while a planar graph is one that admits such a drawing.
- A polyline edge is a chain of segments, and a k-bend drawing allows at most k bends per edge; 0-bend drawings are straight-line drawings.
- The survey uses drawing and topological graph interchangeably, as well as straight-line drawing and geometric graph.
3 Forbidden Configurations and Main Research Directions
Beyond-planar graph families are defined by forbidding specified topological or geometric crossing configurations, and the survey organizes them into a taxonomy of research directions. The families constrain crossings through edge multiplicity, mutual crossing, incidence, angle, partial visibility, and related structures.
- Graph Families: A beyond-planar family consists of graphs admitting drawings that avoid specified forbidden crossing configurations expressing desired crossing properties.
- Crossing Restrictions: k-planar drawings limit each edge to at most k crossings, whereas k-quasi-planar drawings forbid k mutually crossing edges.
- Planarization-Based Families: Skewness-k and k-apex drawings become planar after removing at most k edges or vertices, respectively, with skewness-k implying k-apex.
- Fan-Based Families: Fan-planar drawings forbid two independent edges crossing a third or adjacent edges crossing from different sides, and they can support confluent drawings with fewer crossings per edge.
- Geometric and Visibility Models: Angle- and visibility-based families include RAC drawings, α-angle variants, partial edge drawings, and k-gap-planar drawings with bounded crossings assigned to edges.
- Main Research Directions: The taxonomy groups research directions into first-level categories, refined intermediate nodes, and detailed leaves linked to survey sections and summary tables.
4 Edge Density
Edge-density research asks how many edges beyond-planar graphs can contain under different forbidden crossing configurations, with several tight bounds known but many families unresolved. The survey also distinguishes maximal, maximally dense, and optimal graphs and identifies open density problems.
- Basic density notions: Maximal, maximally dense, and optimal graphs form distinct notions: optimal implies maximally dense, but maximal graphs need not be maximally dense or optimal.
- Density of k-planar graphs: For 1 ≤ k ≤ 4, k-planar graphs have at most (k + 3)(n − 2) edges; the bounds are tight for k = 1 and k = 2.Thus optimal 1-planar and 2-planar graphs have 4n − 8 and 5n − 10 edges, respectively.
- Density of k-quasi-planar graphs: For k-quasi-planar graphs, the conjectured linear bound is proved for k = 3 and k = 4, while k > 4 currently has a c_k n log n upper bound.
- Fan-planar, k-fan-crossing-free, and k-gap graphs: Fan-planar and 1-gap-planar graphs have the tight bound 5n − 10 edges, while fan-crossing-free graphs have at most 4n − 8 topologically and 4n − 9 geometrically.
- Density of straight-line RAC, ACEα, and ACLα graphs: Straight-line RAC graphs have maximum density 4n − 10, with optimal constructions achieving this bound; corresponding ACEα and ACLα bounds are not known to be tight.
- Density of other graph families: A skewness-k graph has at most 3n − 6 + k edges, while k-apex and several grid-free or self-intersection-free families have the stated bounds in the survey.
- Open Problems: Many upper bounds remain non-tight, motivating open problems on tight densities for k-quasi-planar and simple k-planar graphs and lower bounds for maximal straight-line RAC graphs.
5 Recognition
Recognition complexity varies sharply across beyond-planar graph families: many general problems are hard, while fixed parameters or restricted subclasses can yield efficient algorithms. The survey also identifies several unresolved recognition questions.
- Recognition results: Recognizing 1-planar graphs is NP-complete, including when the input has skewness 1 or a fixed rotation system, but optimal 1-planar graphs are recognizable in O(n) time.Recognition is nevertheless fixed-parameter tractable with respect to vertex-cover number, cyclomatic number, or tree-depth.
- Recognition results: Recognizing skewness-k graphs is NP-complete generally but solvable in O(n) time for every fixed k.Thus, the problem is fixed-parameter tractable when parameterized by k.
- Recognition results: Recognition of k-apex graphs is NP-complete, whereas fixed k permits an O(n)-time algorithm; 1-apex graphs additionally have a forbidden-minor characterization whose obstructions are only partly known.Minor closure supplies the existence of a forbidden graph characterization through the Robertson-Seymour theorem.
- Recognition results: Fan-planar and 1-gap-planar recognition are NP-complete, while straight-line RAC recognition is NP-hard and remains unresolved as a membership-in-NP question.Straight-line RAC recognition is linear-time solvable for complete bipartite graphs, and one-crossing-per-edge variants are also NP-hard.
- Open problems: Recognition remains unexplored for many beyond-planar families, including k-quasi-planar graphs, k-bend RAC graphs for k ∈ {1, 2}, and α-SHPEDs.The survey highlights the complexity of k-quasi-planar recognition, k-bend RAC recognition, and α-SHPED recognition as open problems.
6 Stretchability
Stretchability asks when a beyond-planar embedding can be realized with straight edges while preserving its embedding. Beyond Fáry’s theorem for plane graphs, the survey reports partial 1-plane results and several broad open problems.
- Known results: A 1-plane graph has an embedding-preserving straight-line drawing exactly when it contains neither B-configurations nor W-configurations.Figure 5 illustrates these forbidden configurations alongside a 1-plane graph and its embedding-preserving straight-line drawing.
- Open problems: The survey describes stretchability beyond planarity as a fertile, essentially unexplored subject, with open questions for each type of forbidden crossing configuration.It specifically asks for characterizations of stretchable k-quasi-planar and topological skewness-k graphs.
- Open problems: Characterizing stretchable k-quasi-planar topological graphs remains open, including the case k = 3.This is posed as Problem 7 in the survey.
- Open problems: Whether every maximum-degree-three topological graph admits an embedding-preserving straight-line RAC drawing is open.This question concerns embedding preservation together with right-angle crossings, even for structurally simple topological graphs.
- Open problems: For almost-plane graphs, stretchability is characterized only at 3n −5 edges, motivating the open characterization of stretchable topological skewness-k graphs.The latter remains open even for k = 1 when the number of edges is below 3n −5.
7 Relationships Between Graph Families
Beyond-planar graph families overlap in intricate ways: some are incomparable, others satisfy inclusions, and several relationships remain unknown. The survey organizes these results through density, structural, and drawing-property comparisons.
- RAC and 1-planar graphs: Straight-line RAC and 1-planar graphs are incomparable, although every IC-planar graph has a straight-line RAC drawing and some 1-planar graphs do not.Optimal straight-line RAC graphs are 1-planar, while optimal 1-planar graphs are excluded by their larger edge-density bound.
- k-planar and k-quasi-planar graphs: Every k-planar graph is (k + 1)-quasi planar for k ≥ 2, proved by rerouting bundles of pairwise crossing edges; the resulting drawing need not remain k-planar.The relationship was first established for k ≥ 3 and later extended to k = 2.
- k-planar and fan-planar graphs: Fan-planar and k-planar graph families are incomparable: for every k ≥ 2 some fan-planar graph is not k-planar, while some 2-planar graphs are not fan-planar.The fan-planar counterexamples use complete 3-partite graphs K1,3,h.
- Gap-planar relationships: Every 2k-planar graph is k-gap planar, every k-gap planar graph is (2k + 2)-quasi planar, and for fixed k some 1-gap-planar graph is not k-planar.The first inclusion uses Hall’s theorem, while the second follows from a crossing-counting argument.
- Open problems: Open relationship questions include characterizing straight-line RAC graphs that are 1-planar, determining whether k-planar graphs are k-quasi planar, and comparing k-gap-planar with fan-planar graphs.These are posed as Problems 10–12 in the survey.
8 Aesthetics
The survey examines aesthetics beyond crossing restrictions, focusing on edge and vertex complexity, visibility/contact representations, and area–crossing trade-offs. Results show that bends, visibility models, and controlled crossings yield different representational guarantees and area requirements.
- 8.1 Edge Complexity: Every n-vertex 1-plane graph admits an embedding-preserving 1-bend RAC drawing, and a 2-bend RAC drawing can be computed in O(n6) area.For NIC-plane graphs, an embedding-preserving 1-bend RAC drawing exists in quadratic area; embedding-preserving straight-line RAC drawings of kite-triangulations may require Ω(n3) area.
- 8.1 Edge Complexity: Every n-vertex graph has a 3-bend RAC drawing in O(n4) area, while allowing four bends reduces the bound to O(n3) area.For 1-bend and 2-bend RAC drawings, the edge counts are bounded by 6.5n −13 and 74.2n, respectively.
- 8.2 Vertex Complexity: Visibility complexity varies by model: every 1-planar graph has a bar 1-visibility and z-parallel visibility representation, while every IC-planar graph has an L-visibility representation.Every 1-plane graph admits an embedding-preserving ortho-polygon visibility representation, although some 1-plane and IC-plane graphs lack rectangle visibility representations.
- 8.2 Vertex Complexity: Every optimal 1-plane graph has a 3D contact representation using axis-aligned boxes when it has no separating 4-cycles, or L-shaped polyhedra otherwise.The representation uses non-zero-area common boundaries between corresponding vertex polyhedra.
- 8.3 Area-Crossing Trade-offs for Planar Graphs: Allowing crossings can give planar graphs linear-area straight-line drawings, but the crossings may be numerous per edge and have arbitrarily small angles.The cited technique applies to k-colorable graphs for any fixed positive integer k, implying O(n) area for planar graphs.
- 8.3 Area-Crossing Trade-offs for Planar Graphs: Straight-line RAC drawings do not generally reduce planar-graph area below quadratic, although some planar graphs improve from Θ(n2) to Θ(n) area under RAC drawings.Other aesthetics, including uniform edge length and angular resolution, have analogous results; bounded-degree planar graphs also admit 4-bend RAC drawings in O(√∆n) area.
- 8.3 Area-Crossing Trade-offs for Planar Graphs: For outerplanar graphs, fewer crossings per edge require more area: O(n log n) crossings per edge use O(n log n) area, while O(n1−ϵ) crossings per edge use O(n1+ϵ) area.Every planar graph also admits straight-line O(log n)-quasi-planar drawings in O(n log3 n) area or O(log2 n)-quasi-planar drawings in O(n log n) area.
9 Constraints
The survey examines beyond-planar drawings under additional geometric constraints, including layered, circular, outer-boundary, upward, simultaneous, and point-set settings. It reports density, recognition, drawing, and crossing-minimization results, while identifying unresolved recognition and bend-reduction problems.
- Vertices on lines, circles, and external boundary: 2-layer 1-planar and 2-layer RAC graphs coincide at the optimum, with 1.5n−2 edges; linear-time testing and drawing algorithms exist for 2-layer RAC graphs.Recognition of 2-layer fan-planar graphs remains open for graphs that are only 1-connected.
- Vertices on lines, circles, and external boundary: For planar 3-trees and partial 2-trees, linear-time one- and two-page drawings achieve degree-dependent crossing bounds per edge, but no constant bound is possible.The reported bounds are 2∆ crossings per edge for planar 3-trees and ∆2 for partial 2-trees.
- Vertices on lines, circles, and external boundary: Outer 1-planar graphs have a tight density bound of 2.5n −4 edges and can be recognized in linear time, whereas outer fan-planar recognition remains unresolved in general.Maximal outer fan-planar graphs nevertheless admit linear-time recognition.
- Upward RAC Drawings: Upward RAC drawings do not exist for every planar acyclic digraph, and testing whether a planar digraph admits one is computationally difficult.The survey also reports that polynomial-area straight-line upward RAC drawings are not guaranteed.
- Simultaneous RAC embedding: Every pair of planar graphs on the same vertex set admits a simultaneous polyline RAC embedding with at most six bends per edge, while reducing this bound remains open.Without RAC restrictions, simultaneous embeddings can use at most two bends per edge.
- Point-set RAC Embeddings: Every graph with n vertices and m edges admits a point-set RAC embedding on any n × n grid point set with at most three bends per edge in O((n + m)2) area.The result also implies a quadratic-area RAC drawing for every planar graph with at most three bends per edge.
10 Experiments and Engineering
Applied work combines cognitive experiments on crossing configurations with algorithms and visualization systems for beyond-planar drawings. Results link crossing geometry and visual homogeneity to readability, while the survey highlights a continuing lack of user studies for several models.
- Cognitive studies: Sharp crossing angles may trigger extra eye movements and delay path-search tasks, whereas crossings usually have little impact on node-locating tasks.Subsequent studies support large-angle crossings and suggest balancing crossing and vertex angles rather than optimizing one metric alone.
- Cognitive studies: PED user studies suggest that homogeneity improves readability more than fewer crossings and greater ink in the compared heuristic drawings.The comparison concerns heuristic PEDs and the standard 1-SHPED model.
- Algorithms and systems: MAXCIR increases crossing angles through quadratic programming and is reported faster and better than traditional equal-spacing in circular-layout experiments.Other force-directed approaches jointly trade off crossing angles, vertex angles, crossings, bends, and related aesthetics.
- Algorithms and systems: The survey proposes extracting maximum 2-layer RAC subgraphs using heuristics, both with unrestricted vertex orders and with one partition order fixed.These heuristics target layered drawings with large-angle crossings.
- Algorithms and systems: Up to 90% of vertices in computed OPVRs of 1-plane graphs are rectangles with no reflex corners.The underlying algorithm computes embedding-preserving OPVRs with minimum vertex complexity for a fixed embedding.
- Open Problems: A major open issue is the general lack of user studies assessing whether beyond-planar models improve drawing effectiveness in practice.The survey specifically proposes testing whether orthogonal PEDs are more readable than traditional orthogonal drawings.
11 Concluding Remarks
The survey connects beyond-planar graph drawing with crossing minimization, clustered and hybrid visualizations, and edge bundling. It concludes by advocating a user-centered cycle linking experiments, optimization criteria, combinatorial models, algorithms, and renewed evaluation.
- Crossing Minimization: Crossing minimization is NP-complete in general and remains hard for restricted bipartite two-layer straight-line drawings, but it is efficiently solvable for 2-layer RAC graphs.This contrast suggests that other forbidden-crossing models may also admit polynomial-time minimization algorithms.
- Related directions: Beyond-planar ideas connect to clustered planarity, hybrid matrix/node-link visualizations, and edge bundling as approaches to structuring or reducing visual clutter.These connections are presented as related research directions rather than as part of the core beyond-planar literature.
- Concluding remarks: The proposed user-centered research cycle begins with HCI-based theories of reading crossings, then defines optimization criteria, designs algorithms, and experimentally refines the models.The cycle explicitly connects cognitive evidence to combinatorial and algorithmic development.