An annotated bibliography on 1-planarity

DOI10.1016/J.COSREV.2017.06.002zbMath1398.68402arXiv1703.02261OpenAlexW3104418588WikidataQ62042375 ScholiaQ62042375MaRDI QIDQ2407041

Giuseppe Liotta, Stephen G. Kobourov, Fabrizio Montecchiani

Publication date: 28 September 2017

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.02261

zbMATH Keywords

1-planarityannotated bibliographybeyond planar graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (93)

Tree densities in sparse graph classes ⋮ On the Size of Matchings in 1-Planar Graph with High Minimum Degree ⋮ A survey on book-embedding of planar graphs ⋮ Optimal-area visibility representations of outer-1-plane graphs ⋮ On fan-crossing and fan-crossing free graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Packing 1-plane Hamiltonian cycles in complete geometric graphs ⋮ On RAC drawings of 1-planar graphs ⋮ Dynamic list coloring of 1-planar graphs ⋮ Packing Trees into 1-planar Graphs ⋮ The Stub Resolution of 1-planar Graphs ⋮ Drawing outer-1-planar graphs revisited ⋮ Parameterized analysis and crossing minimization problems ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ On quasi-planar graphs: clique-width and logical description ⋮ Partially broken orientations of Eulerian plane graphs ⋮ \((k,p)\)-planarity: a relaxation of hybrid planarity ⋮ On morphing 1-planar drawings ⋮ 1-planar graphs are odd 13-colorable ⋮ Improved product structure for graphs on surfaces ⋮ Straight-line drawings of 1-planar graphs ⋮ Matchings in 1‐planar graphs with large minimum degree ⋮ k-Planar Placement and Packing of Δ-Regular Caterpillars ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs ⋮ The family of fan-planar graphs ⋮ New results on edge partitions of 1-plane graphs ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ Graph product structure for non-minor-closed classes ⋮ Optimal 1-planar multigraphs ⋮ A new note on 1-planar graphs with minimum degree 7 ⋮ On fan-crossing graphs ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ 1-fan-bundle-planar drawings of graphs ⋮ On the curve complexity of 3-colored point-set embeddings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 3D Visibility Representations of 1-planar Graphs ⋮ Gap-Planar Graphs ⋮ Beyond Outerplanarity ⋮ Turning cliques into paths to achieve planarity ⋮ Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles ⋮ Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity ⋮ On the \(k\)-planar local crossing number ⋮ On \((p, 1)\)-total labelling of some 1-planar graphs ⋮ Drawing Subcubic 1-Planar Graphs with Few Bends, Few Slopes, and Large Angles ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Characterizing and recognizing 4-map graphs ⋮ On \((p, 1)\)-total labelling of NIC-planar graphs ⋮ Embedding-preserving rectangle visibility representations of nonplanar graphs ⋮ A structure of 1-planar graph and its applications to coloring problems ⋮ Two-Planar Graphs Are Quasiplanar ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ Edge partitions of optimal 2-plane and 3-plane graphs ⋮ Nonplanar Graph Drawings with k Vertices per Face ⋮ Compact drawings of 1-planar graphs with right-angle crossings and few bends ⋮ Ortho-polygon visibility representations of 3-connected 1-plane graphs ⋮ Gap-planar graphs ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ On the sizes of bipartite 1-planar graphs ⋮ On RAC drawings of graphs with one bend per edge ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ 1-embeddability of complete multipartite graphs on the projective plane ⋮ Spectral extrema of 1-planar graphs ⋮ Min-\(k\)-planar drawings of graphs ⋮ Polyline drawings with topological constraints ⋮ Min-\(k\)-planar drawings of graphs ⋮ Crossing numbers of beyond-planar graphs ⋮ The maximal 1-planarity and crossing numbers of graphs ⋮ Non-1-planarity of lexicographic products of graphs ⋮ Crossing numbers of beyond-planar graphs ⋮ Edge-minimum saturated \(k\)-planar drawings ⋮ Re-1-embeddings of optimal 1-embedded graphs on the projective plane ⋮ Unnamed Item ⋮ Better bounds for poset dimension and boxicity ⋮ Equitable partition of plane graphs with independent crossings into induced forests ⋮ On Layered Fan-Planar Graph Drawings ⋮ On 3D visibility representations of graphs with few crossings per edge ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ 1-Planar Graphs ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study ⋮ From light edges to strong edge-colouring of 1-planar graphs ⋮ A note on the upper bounds on the size of bipartite and tripartite 1-embeddable graphs on surfaces ⋮ Counting cliques in 1-planar graphs ⋮ The structure and the list 3-dynamic coloring of outer-1-planar graphs ⋮ 1-planar graphs without 4-cycles or 5-cycles are 5-colorable

Uses Software

• gCol

Cites Work

• Outer 1-planar graphs
• Recognizing and drawing IC-planar graphs
• Simultaneous visibility representations of plane \(st\)-graphs using L-shapes
• On drawings and decompositions of 1-planar graphs
• A note on 1-planar graphs
• 1-planarity of complete multipartite graphs
• On edge colorings of 1-planar graphs without adjacent triangles
• Sparsity. Graphs, structures, and algorithms
• Edge covering pseudo-outerplanar graphs with forests
• Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
• Joins of 1-planar graphs
• Drawing complete multipartite graphs on the plane with restrictions on crossings
• A linear-time algorithm for testing outer-1-planarity
• On partitioning the edges of 1-plane graphs
• Characterisations and examples of graph classes with bounded expansion
• List edge and list total coloring of 1-planar graphs
• Drawing graphs with right angle crossings
• Ortho-polygon visibility representations of embedded graphs
• An upper bound on the number of edges in an almost planar bipartite graph
• A linear-time algorithm for 7-coloring 1-plane graphs
• On miniaturized problems in parameterized complexity theory
• The structure of 1-planar graphs
• L-visibility drawings of IC-planar graphs
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• On an extremal problem in the class of bipartite 1-planar graphs
• Optimal 1-planar graphs which triangulate other surfaces
• Representing a planar graph by vertical lines joining different levels
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Embedding planar graphs in four pages
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• Bemerkungen zu einem Sechsfarbenproblem von G. Ringel
• Graphs drawn with few crossings per edge
• Advances in the theory and practice of graph drawing
• Algorithms for drawing graphs: An annotated bibliography
• Circle packings of maps in polynomial time
• New results on edge partitions of 1-plane graphs
• Simultaneous embedding of a planar graph and its dual on the grid
• Surfaces, tree-width, clique-minors, and partitions
• Empirical evaluation of aesthetics-based graph layout
• Star arboricity of graphs
• Outerplanar partitions of planar graphs
• The structure of plane graphs with independent crossings and its applications to coloring problems
• Density of straight-line 1-planar graph drawings
• On edge colorings of \(1\)-planar graphs
• Right angle crossing graphs and 1-planarity
• On total colorings of 1-planar graphs
• Ein Sechsfarbenproblem auf der Kugel
• On RAC drawings of 1-planar graphs
• Layered separators in minor-closed graph classes with applications
• The book thickness of 1-planar graphs is constant
• \(\mathsf{NIC}\)-planar graphs
• A note on total colorings of 1-planar graphs
• Algorithms for graphs embeddable with few crossings per edge
• Recognizing hole-free 4-map graphs in cubic time
• Generation of simple quadrangulations of the sphere
• Parameterized Complexity of 1-Planarity
• On properties of maximal 1-planar graphs
• Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
• Fáry’s Theorem for 1-Planar Graphs
• 1-Visibility Representations of 1-Planar Graphs
• Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs
• The Book Embedding Problem from a SAT-Solving Perspective
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Re-embeddings of Maximum 1-Planar Graphs
• Coloring plane graphs with independent crossings
• Map graphs
• Über 1-optimale Graphen
• Contact Representations of Graphs in 3D
• A Guide to Graph Colouring
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Chromatic number, independence ratio, and crossing number
• On local structure of 1-planar graphs of minimum degree 5 and girth 4
• Edge partition of planar sraphs into two outerplanar graphs
• New bounds on the edge number of ak-map graph
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• Every planar map is four colorable
• Approximation algorithms for NP-complete problems on planar graphs
• Graphs with E Edges Have Pagenumber O(√E)
• Graph Drawing and Applications for Software and Knowledge Engineers
• Recognizing IC-Planar and NIC-Planar Graphs
• Representations of Planar Graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• A new proof of the 6 color theorem
• On the Density of Maximal 1-Planar Graphs
• Testing Maximal 1-Planarity of Graphs with a Rotation System in Linear Time
• Drawing graph joins in the plane with restrictions on crossings
• 1-Planarity of Graphs with a Rotation System
• EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
• The Number of Edges in $k$-Quasi-planar Graphs
• Bar k-Visibility Graphs
• Structure of Graphs with Locally Restricted Crossings
• Coupled choosability of plane graphs
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• The Two-Triangle Case of the Acquaintance Graph
• Graph-Theoretic Concepts in Computer Science
• Drawing Outer 1-planar Graphs with Few Slopes
• Drawing graphs. Methods and models
• Acyclic colouring of 1-planar graphs
• gCol
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An annotated bibliography on 1-planarity