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

DOI10.1007/978-3-319-50106-2_25MaRDI QIDQ2961525zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: Thomassen characterized some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph is drawable in straight-lines if and only if it does not contain the configuration [C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory, 10(3), 335-341, 1988]. In this paper, we characterize some 1-plane embedding as the forbidden configuration such that a given 1-plane embedding of a graph can be re-embedded into a straight-line drawable 1-plane embedding of the same graph if and only if it does not contain the configuration. Re-embedding of a 1-plane embedding preserves the same set of pairs of crossing edges. We give a linear-time algorithm for finding a straight-line drawable 1-plane re-embedding or the forbidden configuration.

Recommendations

• Re-embedding a 1-plane graph for a straight-line drawing in linear time
• Embedding rectilinear graphs in linear time
• Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
• Planar rectilinear drawings of outerplanar graphs in linear time
• scientific article; zbMATH DE number 1256757
• An algorithm for straight-line drawing of planar graphs
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Graph Drawing
• A linear-time algorithm for drawing a planar graph on a grid
• On a straight-line embedding problem of graphs

Cites work

• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Algorithms for graphs embeddable with few crossings per edge
• Dividing a Graph into Triconnected Components
• Ein Sechsfarbenproblem auf der Kugel
• Fáry's theorem for 1-planar graphs
• Graphs drawn with few crossings per edge
• On-Line Planarity Testing
• Outer 1-planar graphs
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Rectilinear drawings of graphs
• The structure of 1-planar graphs

Cited in

(9)

• 1-planarity testing and embedding: an experimental study
• Re-embedding a 1-plane graph for a straight-line drawing in linear time
• An annotated bibliography on 1-planarity
• Fáry's theorem for 1-planar graphs
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Beyond planar graphs: introduction
• Quantitative restrictions on crossing patterns
• Algorithms for 1-Planar Graphs
• Hanani-Tutte for approximating maps of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961525)