A linear-time algorithm for testing full outer-2-planarity

DOI10.1016/J.DAM.2018.08.018MaRDI QIDQ1727743zbMATH OpenOpenAlexFDO

Authors Seok-Hee Hong, Hiroshi Nagamochi

Publication date 20 February 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.08.018

zbMATH Keywords

full-outer-2-planar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Testing Full Outer-2-planarity in Linear Time
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity
• Recognizing outer 1-planar graphs in linear time
• Planar rectilinear drawings of outerplanar graphs in linear time

Cites work

• scientific article; zbMATH DE number 3924797 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (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
• Algorithms for graphs embeddable with few crossings per edge
• Drawing graphs with right angle crossings
• Efficient Planarity Testing
• Fan-planarity: properties and complexity
• Fáry's theorem for 1-planar graphs
• Graphs drawn with few crossings per edge
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• On-Line Planarity Testing
• Parameterized complexity of 1-planarity
• Quasi-planar graphs have a linear number of edges
• Rectilinear drawings of graphs
• Straight-Line Drawability of a Planar Graph Plus an Edge
• Testing Full Outer-2-planarity in Linear Time
• The number of edges in \(k\)-quasi-planar graphs
• The straight-line RAC drawing problem is NP-hard

Cited in

(16)

• Recognizing and embedding simple optimal 2-planar graphs
• On RAC drawings of graphs with one bend per edge
• 2-Layer k-Planar Graphs
• Algorithms for 1-Planar Graphs
• Beyond outerplanarity
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• A linear-time algorithm for testing outer-1-planarity
• A direct linear-time planarity test for unflippable modules
• Fully-dynamic planarity testing in polylogarithmic time
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• Beyond planar graphs: introduction
• Testing Full Outer-2-planarity in Linear Time
• An algorithm for an 𝓁²-homological test for the planarity of a graph
• The density of fan-planar graphs
• A linear-time algorithm for testing outer-1-planarity
• scientific article; zbMATH DE number 1377359 (Why is no real title available?)

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

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