Algorithms for 1-Planar Graphs

DOI10.1007/978-981-15-6533-5_5OpenAlexW3089606299MaRDI QIDQ5001657

Seok-Hee Hong

Publication date: 22 July 2021

Published in: Beyond Planar Graphs (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-981-15-6533-5_5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (2)

Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ 1-planarity testing and embedding: an experimental study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Outer 1-planar graphs
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• How to draw a planar graph on a grid
• The structure of 1-planar graphs
• An algorithm for constructing star-shaped drawings of plane graphs
• Optimal 1-planar graphs which triangulate other surfaces
• Graphs drawn with few crossings per edge
• A linear-time algorithm for testing full outer-2-planarity
• On-line maintenance of triconnected components with SPQR-trees
• On edge colorings of \(1\)-planar graphs
• Ein Sechsfarbenproblem auf der Kugel
• Algorithms for graphs embeddable with few crossings per edge
• On properties of maximal 1-planar graphs
• Fáry’s Theorem for 1-Planar Graphs
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Re-embeddings of Maximum 1-Planar Graphs
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• Parameterized Complexity of 1-Planarity
• 1-Planarity of Graphs with a Rotation System
• Adding One Edge to Planar Graphs Makes Crossing Number and 1-Planarity Hard
• Acyclic colouring of 1-planar graphs

This page was built for publication: Algorithms for 1-Planar Graphs