A linear-time algorithm for testing outer-1-planarity

DOI10.1007/S00453-014-9890-8MaRDI QIDQ494794zbMATH OpenOpenAlexWikidataFDO

Authors Seok-Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, P. Schweitzer, Yusuke Suzuki

Publication date 2 September 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-014-9890-8

zbMATH Keywords

graph drawing1-planarity1-planar embedding1-planar graphsouter 1-planar graphs

Mathematics Subject Classification ID

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

Recommendations

• A linear-time algorithm for testing outer-1-planarity
• Recognizing outer 1-planar graphs in linear time
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing full outer-2-planarity
• Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)

Cites work

• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 3924797 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Adding one edge to planar graphs makes crossing number and 1-planarity hard
• Algorithms for graphs embeddable with few crossings per edge
• Dividing a Graph into Triconnected Components
• Drawing outerplanar graphs using three edge lengths
• Ein Sechsfarbenproblem auf der Kugel
• Every outer-1-plane graph has a right angle crossing drawing
• Fáry's theorem for 1-planar graphs
• Graphs drawn with few crossings per edge
• Mathematical Foundations of Computer Science 2003
• On-line maintenance of triconnected components with SPQR-trees
• Optimal 1-planar graphs which triangulate other surfaces
• Parameterized complexity of 1-planarity
• Re-embeddings of Maximum 1-Planar Graphs
• Recognizing outer 1-planar graphs in linear time
• Rectilinear drawings of graphs
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Straight-line drawings of outerplanar graphs in \(O(dn \log n)\) area
• Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)
• The book thickness of a graph
• The structure of 1-planar graphs
• \(h\)-quasi planar drawings of bounded treewidth graphs in linear area

Cited in

(39)

• Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
• Re-embedding a 1-plane graph for a straight-line drawing in linear time
• Recognizing and embedding simple optimal 2-planar graphs
• Recognizing outer 1-planar graphs in linear time
• 2-Layer k-Planar Graphs
• A Planarity Test via Construction Sequences
• scientific article; zbMATH DE number 4049084 (Why is no real title available?)
• Linear arboricity of outer-1-planar graphs
• Algorithms for 1-Planar Graphs
• Nonplanar Graph Drawings with k Vertices per Face
• 1-planarity testing and embedding: an experimental study
• Beyond outerplanarity
• An experimental study of a 1-planarity testing and embedding algorithm
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• Characterizing and recognizing 4-map graphs
• Strong Edge Coloring of Outerplane Graphs with Independent Crossings
• A linear-time algorithm for testing outer-1-planarity
• On fan-crossing and fan-crossing free graphs
• Gap-Planar Graphs
• Optimal-area visibility representations of outer-1-plane graphs
• A direct linear-time planarity test for unflippable modules
• Testing maximal 1-planarity of graphs with a rotation system in linear time (extended abstract)
• \(\mathsf{NIC}\)-planar graphs
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• On Aligned Bar 1-Visibility Graphs
• Fully-dynamic planarity testing in polylogarithmic time
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• An annotated bibliography on 1-planarity
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Recognizing optimal 1-planar graphs in linear time
• Beyond planar graphs: introduction
• Testing Full Outer-2-planarity in Linear Time
• Gap-planar graphs
• A linear-time algorithm for testing full outer-2-planarity
• Outer 1-planar graphs
• scientific article; zbMATH DE number 1377359 (Why is no real title available?)
• Recognizing IC-planar and NIC-planar graphs
• Remarks on the joins of 1-planar graphs
• On the computational complexity of upward and rectilinear planarity testing

This page was built for publication: A linear-time algorithm for testing outer-1-planarity

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