An annotated bibliography on 1-planarity

1 Introduction

• Good graph drawings support readability and understanding, while planar-focused algorithms have had little impact on visualizing complex non-planar networks.The paper identifies beyond-planar drawing algorithms as being in high demand.Source: §1 · p. 2
• A 1-planar graph has an embedding in which each edge is crossed at most once; Ringel introduced the class in 1965, and Borodin proved its chromatic number is at most 6.Ringel had proved a bound of 7 and conjectured 6; the bound of 6 is tight because K6 is 1-planar and needs six colors.Source: §1 · p. 2
• References appear in the main text to guide readers through results, with a complete bibliography collected at the paper’s end.Source: §1 · p. 2
• The bibliography covers characterization and recognition, structural properties such as coloring and edge density, and geometric representations including straight-line and contact drawings.It also surveys visibility representations and drawings with right-angle crossings.Source: §1 · pp. 2–3

2.1 Basic definitions

• Section 2.1 reviews basic graph-theoretic and graph-drawing definitions for readers who need them.The review is intended to make the paper self-contained.Source: §2.1 · p. 3

2.1.1 Graphs

• A graph consists of vertices and edges; the preliminaries also define subgraphs, connectivity, cycles, trees, complete graphs, and multipartite graphs.Graphs are treated as simple unless stated otherwise.Source: §2.1.1 · p. 4

2.1.2 Drawings and Embeddings

• Drawings map vertices to points and edges to curves; planar drawings have no edge crossings, while planarization replaces crossings with dummy vertices.The section also defines straight-line, polyline, and grid drawings, embeddings, and rotation systems.Source: §2.1.2 · pp. 4–5

2.2 1-planar Graphs

• A 1-planar drawing allows each edge to be crossed at most once; subclasses include outer 1-planar, optimal, maximum, maximal, triangulated, IC-planar, and NIC-planar graphs.An n-vertex 1-planar graph has at most 4n −8 edges; equality defines optimality, while maximum means having the greatest edge count among such graphs.Source: §2.2 · pp. 5–6

3.1.1 General 1-planar graphs

• General 1-planar graphs are not minor-closed, and exponentially many minimal non-1-planar graphs make finite forbidden-minor characterizations unlikely.Every graph has a 1-planar subdivision, ruling out a finite forbidden-subdivision characterization as well.Source: §3.1.1 · pp. 6–7

3.1.2 Optimal 1-planar graphs

• An n-vertex 1-planar graph is optimal exactly when it has 4n −8 edges and arises by adding a crossing pair inside every face of a 3-connected planar quadrangulation.This gives a one-to-one correspondence with 3-connected planar quadrangulations; every such quadrangulation, and its corresponding optimal graph, can be generated from the pseudo double wheel family by vertex-splitting and 4-cycle additions. These operations must preserve simplicity and triconnectivity.Source: §3.1.2 · pp. 7–9

3.1.3 Triangulated 1-planar graphs

• A 3-connected graph is triangulated 1-planar exactly when it is realizable as a hole-free 4-map.The 1-planar class includes 4-map graphs, but the reverse inclusion does not hold.Source: §3.1.3 · p. 9

3.1.4 Complete k-partite 1-planar graphs

• For complete multipartite graphs, K_n1,n2 is not 1-planar when both parts are at least 5; K_n1,3 is 1-planar iff n1 ≤6, and K_n1,4 iff n1 ≤4.Source: §3.1.4 · p. 10

3.2.1 NP-hardness results

• General 1-planarity recognition is NP-complete, and remains NP-complete for bounded bandwidth, pathwidth, or treewidth and planar graphs augmented by one edge.Source: §3.2.1 · pp. 10–11

3.2.2 Polynomial-time results

• Restricted classes admit polynomial-time recognition: optimal 1-planar graphs in O(n), triangulated 1-planar and triangulated IC/NIC-planar graphs in cubic time, and optimal NIC-planar graphs in linear time.For outer 1-planar graphs, O(n)-time algorithms return an embedding when the input is positive; one algorithm also returns one of six non-outer-1-planar minors when negative.Source: §3.2.2 · pp. 11–12

3.2.3 Fixed rotation system setting

• With a fixed rotation system, recognition remains NP-complete even for 3-connected graphs, while maximal 1-planar embeddings respecting it can be tested in O(n).Source: §3.2.3 · p. 12

3.2.4 Parameterized complexity

• 1-planarity is fixed-parameter tractable by cover number, tree-depth, and cyclomatic number.Source: §3.2.4 · p. 13

• The section reviews classic coloring results and bounds on the number of edges in 1-planar graphs.Source: §4 · p. 13
• It covers edge partitions, bounds on graph parameters, and the existence of subgraphs with bounded vertex degree.Source: §4 · p. 13
• It also surveys binary graph operations that preserve 1-planarity.Source: §4 · p. 13

4.1 Coloring

• The section frames coloring as assigning colors to vertices, edges, or both subject to constraints, with applications including scheduling and frequency assignment.Source: §4.1 · p. 13

4.1.1 Vertex coloring

• Every 1-planar graph has chromatic number at most 6, a tight bound since K6 requires six colors.A linear-time algorithm computes a 7-coloring, while deciding 4-colorability is NP-complete.Source: §4.1.1 · p. 14

4.1.2 Edge coloring

• For maximum degree ∆≥10, every 1-planar graph has chromatic index ∆.Results also give ∆-colorings under restrictions on triangles or chordal 5-cycles, and for IC-planar graphs at ∆≥8 [43].Source: §4.1.2 · p. 15

4.1.3 Total coloring

• Zhang et al. proved the total coloring conjecture for 1-planar graphs with maximum vertex degree ∆≥13; Czap showed their total chromatic number is at most ∆+ 3 for ∆≥10.Every 1-planar graph has a list total coloring with ∆+ 2 colors if ∆≥16 and ∆+ 1 colors if ∆≥21; if G is IC-planar and ∆≥8, it has a list total coloring with ∆+ 1 colors.Source: §4.1.3 · p. 16

4.2 Edge density

• A 1-planar graph has at most 4n −8 edges, and this bound is tight for n=8 and n≥10.An optimal graph reaches the bound by adding two crossing edges in each face of an underlying planar quadrangulation.Source: §4.2 · p. 16
• A 1-planar graph admitting a straight-line 1-planar drawing has at most 4n−9 edges.Source: §4.2 · p. 17
• IC-planar graphs have at most 3.25n−6 edges, while NIC-planar graphs have at most 3.6n −7.2; both bounds are tight.Source: §4.2 · p. 17
• Outer 1-planar graphs have at most 2.5n −4 edges, while maximal ones have at least 2.2n −3.6 edges; both bounds are tight.Source: §4.2 · p. 18
• Bipartite 1-planar graphs have tight upper bounds of 3n −8 for even n except 6, and 3n −9 for odd n and n=6.For an unbalanced bipartition whose smaller part is sublinear in n, the edge count is (2 + o(1))n.Source: §4.2 · p. 18

4.3 Edge partitions

• Every 1-planar graph admits an edge partition whose red and blue graphs are planar, and the red graph can be a forest.The partition colors one edge from each crossing pair red and the remaining edges blue.Source: §4.3 · p. 19
• For optimal 1-planar graphs, requiring the red graph to be a forest can force arbitrarily large maximum degree, whereas dropping that requirement permits maximum degree 4.For 3-connected 1-planar graphs, maximum red degree six is sufficient and sometimes necessary; some 2-connected examples require degree Ω(n).Source: §4.3 · p. 19
• Every NIC-plane graph has a partition with red maximum degree three, which is worst-case optimal; deciding whether degree two is possible is NP-complete.For degree one, deciding whether a partition exists and finding one when it does takes O(n^2) time.Source: §4.3 · pp. 19–20

4.4.1 Book thickness

• Book thickness is at most 16 for general 1-planar graphs and 12 for 3-connected ones; examples attain 4, while experiments did not confirm a hypothesized need for five pages.A general O(√n) upper bound also follows from the O(√m) bound for graphs with m edges; planar graphs have book thickness at most 4, though no planar graph requiring four pages is known.Source: §4.4.1 · p. 21

4.4.2 Treewidth

• 1-planar graphs on n vertices have pathwidth and treewidth O(√n), implying 1/2-separators of size O(√n); they also have layered treewidth at most 12.Related balanced-separator bounds were used to show that many optimization problems admit PTASs on these graphs.Source: §4.4.2 · pp. 21–22

4.4.3 Expansion

• 1-planar graphs have bounded expansion, also implied by their O(√n)-size 1/2-separators.Bounded expansion is defined through edge-to-vertex ratios in t-shallow minors; polynomial expansion implies PTASs for several optimization problems.Source: §4.4.3 · p. 22

4.5 Subgraphs with bounded vertex degree

• Every 1-planar graph contains a vertex of degree at most 7, and every 3-connected 1-planar graph contains an edge whose endpoints both have degree at most 20.For minimum degree at least 4, a 1-planar graph contains an edge with endpoint degrees (4, at most 13), (5, at most 9), (6, at most 8), or (7, 7).Source: §4.5 · p. 22
• A 1-planar graph of minimum degree 5 and girth 4 contains a degree-5 vertex adjacent to one of degree at most 6, a 4-cycle with all degrees at most 9, and a K1,4 whose vertices all have degree at most 11.Source: §4.5 · p. 23
• An optimal 1-planar graph with at least k vertices contains a k-vertex path whose degree sum is at most 8k − 1; a 3-connected maximal one with at least 2k vertices contains a k-vertex path with each degree at most 10k.Source: §4.5 · p. 23

4.6 Binary operations

• When both graphs have at least three vertices, their join is 1-planar exactly when the pair is subgraph-majorized by one of four specified pairs: [C3 ∪ C3, C3], [C4, C4], [C4, C3], or [K2,1,1, P3].Subgraph-majorized means both graphs are subgraphs of graphs of the major pair.Source: §4.6 · p. 23
• If G has minimum vertex degree three and H is a single vertex, then G ◦ H is 1-planar if and only if G is 1-planar.The lexicographic product is not commutative in general.Source: §4.6 · p. 23

5.1 Straight-line drawings

• A 1-plane graph has an embedding-preserving straight-line drawing exactly when it contains neither B- nor W-configurations; testing and drawing can be done in linear time.Such drawings may require exponential area; re-embedding while preserving crossing pairs can also be tested in linear time.Source: §5.1 · p. 24
• A 3-connected 1-planar graph has a grid drawing with straight edges except for at most one outer-face edge requiring one bend; the drawing has O(n) × O(n) area and is computed in O(n) time.The preprocessing may change the input embedding by adding edges and rerouting an edge to remove a B-configuration.Source: §5.1 · p. 25
• Any 1-planar graph with a 1-planar straight-line drawing has at most 4n − 9 edges, a tight bound; since 1-planar graphs can have 4n − 8 edges, some admit no such drawing in any embedding.Source: §5.1 · p. 25
• Every IC-plane graph has a 1-planar straight-line drawing on an O(n^2) × O(n^2) grid, computable in O(n) time.The augmentation makes the graph 3-connected and may change its embedding, while retaining IC-planarity.Source: §5.1 · p. 25
• Every outer 1-planar graph of maximum degree Δ has an outer 1-planar straight-line drawing with O(Δ) slopes, computable in O(n) time; it also has a planar straight-line drawing with at most O(Δ^2) slopes.Source: §5.1 · p. 25
• A 3-connected planar graph and its dual can be drawn on a (2n − 2) × (2n − 2) grid in O(n) time, with straight edges except for one outer-face edge and crossings only between primal-dual pairs.Source: §5.1 · p. 26
• Every n-vertex 1-planar graph has a crossing-free straight-line 3D drawing with integer-coordinate vertices and occupied volume O(n log n).The result follows from layered treewidth at most 12, track-number O(log n), and a proper coloring with at most six colors.Source: §5.1 · p. 26

5.2 RAC drawings

• RAC drawings require crossings at right angles, a condition motivated by cognitive experiments on crossing-angle readability.Source: §5.2 · p. 26

5.2.1 Straight-line RAC drawings

• Straight-line RAC representations have distinct class boundaries: all IC-planar graphs admit them, but general 1-planar graphs do not always.Every outer 1-planar graph also has an embedding-preserving straight-line RAC drawing [51].Source: §5.2.1 · p. 27

5.2.2 k-bend RAC drawings with k > 0

• Every 1-planar graph has a 1-bend RAC drawing computable in O(n) time, though the algorithm may change the embedding and use exponential area.Source: §5.2.2 · p. 28

5.3 Visibility representations

• Visibility models extend bar representations for nonplanar graphs through edge visibility across vertices or more complex vertex shapes and two orthogonal edge directions.Source: §5.3 · p. 29

5.3.1 Bar 1-visibility representations

• Every n-vertex 1-planar graph has a bar 1-visibility representation on an O(n) × O(n) grid, constructible in linear time with possible embedding changes.Source: §5.3.1 · p. 29

5.3.2 L-visibility representations

• Every n-vertex IC-plane graph has an L-visibility representation in O(n^2) area, computable in O(n) time, with each visibility crossed at most once.No two crossed visibilities are incident to the same L-shape.Source: §5.3.2 · p. 30

5.3.3 Rectangle visibility representations

• A 1-plane graph has an embedding-preserving rectangle visibility representation exactly when it lacks B-, W-, and T-configurations; this can be tested and constructed in O(n) time.Some 1-planar graphs lack such representations for every embedding unless a linear number of edges are removed.Source: §5.3.3 · p. 30

5.3.4 Ortho-polygon visibility representations

• Every 1-plane graph admits an embedding-preserving ortho-polygon visibility representation on an O(n) × O(n) grid, computable in O(n) time.For 3-connected graphs, at most 12 reflex corners per vertex suffice; some 2-connected 1-planar graphs require linearly many at some vertices.Source: §5.3.4 · p. 31

5.4 Contact representations

• Every n-vertex optimal 1-planar graph has an L-contact representation computable in O(n^2) time, while box-contact representations are computable in O(n) time when there are no separating 4-cycles.Not every optimal 1-planar graph admits a box-contact representation.Source: §5.4 · p. 31

6 Final Remarks and Open Problems

• The bibliography surveys results on recognizing and characterizing 1-planar graphs, their structural properties, and their geometric representations [p].Source: §6 · pp. 31–32
• Recognition questions include which classes are polynomial-time recognizable, the complexity for bounded-degree graphs, and practical recognition algorithms.Source: §6 · p. 32
• The survey also asks about coloring complexity, book thickness, straight-line drawings with convex faces, and degree bounds for straight-line RAC drawings.Source: §6 · pp. 32–33
• Open structural questions ask whether crossing edges can be two-colored into forests, what the star arboricity is, and how large maximum matchings can be in 1-planar graphs.Source: §6 · p. 32
• Geometric open problems include recognition of bar 1-visibility graphs, tight reflex-corner bounds for ortho-polygon representations, and L-contact representations beyond optimal graphs.Source: §6 · p. 33
• The authors call for more attention to 3D representations of 1-planar graphs beyond the limited results in Sections 5.1 and 5.4.Source: §6 · p. 33