Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time

DOI10.1007/978-3-319-50106-2_25zbMath1478.68244arXiv1608.07662OpenAlexW2964068915MaRDI QIDQ2961525

Seok-Hee Hong, Hiroshi Nagamochi

Publication date: 21 February 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

An annotated bibliography on 1-planarity ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Hanani-Tutte for approximating maps of graphs ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ Algorithms for 1-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study

Cites Work

• 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
• The structure of 1-planar graphs
• Graphs drawn with few crossings per edge
• Ein Sechsfarbenproblem auf der Kugel
• Algorithms for graphs embeddable with few crossings per edge
• Fáry’s Theorem for 1-Planar Graphs
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Rectilinear drawings of graphs
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components

This page was built for publication: Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time